接水果(fruit)

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define maxn 320005
using namespace std;
int n,P,Q,head[maxn],tot,sc,dft[maxn],dfn[maxn];
int deep[maxn],f[maxn][22],top,Max,q[maxn],ans[maxn];
int tr[maxn],tx[maxn],tp,cnt,dy[maxn];
map<int,int>ls;
struct node{
    int v,nex;
}e[maxn*2];
struct sq{
    int fl,pl,a,b,v,val;
}a[maxn],b[maxn];
void lj(int t1,int t2){
    e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;
}
void dfs(int k,int fa){
    dft[k]=++sc;deep[k]=deep[fa]+1;f[k][0]=fa;
    for(int i=head[k];i;i=e[i].nex){
        if(e[i].v!=fa)dfs(e[i].v,k);
    }
    dfn[k]=sc;
}
int Lca(int u,int v){
    if(deep[u]<deep[v])swap(u,v);
    for(int x=20;x>=0;x--)if(deep[f[u][x]]>=deep[v])u=f[u][x];
    for(int x=20;x>=0;x--)if(f[u][x]!=f[u][x])u=f[u][x],v=f[v][x];
    return u==v?u:f[u][0];
}
bool cmp(sq a,sq b){
    return a.pl<b.pl||(a.pl==b.pl&&a.fl<b.fl);
}
void add(int i,int v){
    for(;i<=n;i+=i&-i)tr[i]+=v;
}
int ask(int i){
    int sum=0;
    for(;i;i-=i&-i)sum+=tr[i];
    return sum;
}
void add(int xa,int xb,int ya,int yb,int w){
    if(xa>xb||ya>yb||ya<0||xa<0)return;
    a[++top]=(sq){0,xa,ya,yb,w,1};
    a[++top]=(sq){0,xb+1,ya,yb,w,-1};
}
void lsh(){
    sort(tx+1,tx+tp+1);
    cnt=0;
    for(int i=1;i<=tp;i++)
        if(!ls[tx[i]])ls[tx[i]]=++cnt,dy[cnt]=tx[i];
}
void solve(int l,int r,int ql,int qr){
    if(ql>qr)return;
    if(l==r){
        for(int i=ql;i<=qr;i++){
            if(a[i].fl>0)ans[a[i].fl]=l;
        }
        return;
    }
    int mid=l+r>>1;
    for(int i=ql;i<=qr;i++){
        if(a[i].fl>0){
            q[i]=ask(a[i].a);
        }
        else {
            if(a[i].v<=mid){
                add(a[i].a,a[i].val);add(a[i].b+1,-a[i].val);
            }
        }
    }
    for(int i=ql;i<=qr;i++){
        if(a[i].fl==0){
            if(a[i].v<=mid){
                add(a[i].a,-a[i].val);add(a[i].b+1,a[i].val);
            }
        }
    }
    int t=ql-1;
    for(int i=ql;i<=qr;i++){
        if(a[i].fl>0){
            if(q[i]>=a[i].v)b[++t]=a[i];
        }
        else {
            if(a[i].v<=mid)b[++t]=a[i];
        }
    }
    int ff=t;
    for(int i=ql;i<=qr;i++){
        if(a[i].fl>0){
            if(q[i]<a[i].v){
                a[i].v-=q[i];
                b[++t]=a[i];
            }
        }
        else {
            if(a[i].v>mid)b[++t]=a[i];
        }
    }
    for(int i=ql;i<=qr;i++)a[i]=b[i];
    solve(l,mid,ql,ff);solve(mid+1,r,ff+1,qr);
}
int main()
{
    cin>>n>>P>>Q;
    for(int i=1,t1,t2;i<n;i++){
        scanf("%d%d",&t1,&t2);
        lj(t1,t2);lj(t2,t1);
    }
    dfs(1,0);
    for(int j=1;j<=20;j++)
    for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1,u,v,w;i<=P;i++){
        scanf("%d%d%d",&u,&v,&w);
        tx[++tp]=w;
        if(deep[u]<deep[v])swap(u,v);
        int lca=Lca(u,v);
        if(lca==v){
            int dep=deep[u]-deep[v]-1;
            int t=u;
            for(int x=20;x>=0;x--){
                if((1<<x)<=dep){
                    t=f[t][x];dep-=(1<<x);
                }
            }
            add(dft[u],dfn[u],1,dft[t]-1,w);
            add(1,dft[t]-1,dft[u],dfn[u],w);
            
            add(dft[u],dfn[u],dfn[t]+1,n,w);
            add(dfn[t]+1,dft[u],dfn[u],n,w);
        }
        else {
            add(dft[u],dfn[u],dft[v],dfn[v],w);
            add(dft[v],dfn[v],dft[u],dfn[u],w);
        }
    }
    lsh();
    for(int i=1,t1,t2,t3;i<=Q;i++){
        scanf("%d%d%d",&t1,&t2,&t3);
        a[++top].fl=i;
        a[top].pl=dft[t2];a[top].a=dft[t1];a[top].v=t3;
    }
    sort(a+1,a+top+1,cmp);
    for(int i=1;i<=top;i++){
        if(!a[i].fl)a[i].v=ls[a[i].v];
    }
    solve(1,cnt,1,top);
    for(int i=1;i<=Q;i++){
        printf("%d\n",dy[ans[i]]);
    }
    return 0;
}