code:
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#define N 50003
using namespace std;
void setIO(string s) {
string in=s+".in";
string out=s+".out";
freopen(in.c_str(),"r",stdin);
// freopen(out.c_str(),"w",stdout);
}
namespace BIT {
int C[N];
int lowbit(int t) {
return t&(-t);
}
void update(int x,int v) {
for(;x<N;x+=lowbit(x)) {
C[x]+=v;
}
}
int query(int x) {
int tmp=0;
for(;x>0;x-=lowbit(x)) {
tmp+=C[x];
}
return tmp;
}
void clr(int x) {
for(;x<N;x+=lowbit(x)) {
C[x]=0;
}
}
};
int n,P,Q;
int dfn;
int edges;
int hd[N],to[N<<1],nex[N<<1];
int fa[20][N];
int st[N],ed[N],dep[N];
int A[N];
int answer[N];
struct data {
int x1;
int y1;
int x2;
int y2;
int val;
data(int x1=0,int y1=0,int x2=0,int y2=0,int val=0):x1(x1),y1(y1),x2(x2),y2(y2),val(val){}
}t[N],tmp1[N],tmp2[N];
struct qu {
int x,y,id,kth;
qu(int x=0,int y=0,int id=0,int kth=0):x(x),y(y),id(id),kth(kth){}
}as[N],gl[N],gr[N];
struct Seg {
int x,l,r,d;
Seg(int x=0,int l=0,int r=0,int d=0):x(x),l(l),r(r),d(d){}
}sg[N];
bool cmp_seg(Seg a,Seg b) {
return a.x<b.x;
}
bool cmp_qu(qu a,qu b) {
return a.x<b.x;
}
void add(int u,int v) {
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void dfs(int u,int ff) {
fa[0][u]=ff;
for(int i=1;i<20;++i) {
fa[i][u]=fa[i-1][fa[i-1][u]];
}
st[u]=++dfn;
dep[u]=dep[ff]+1;
for(int i=hd[u];i;i=nex[i]) {
int v=to[i];
if(v==ff) {
continue;
}
dfs(v,u);
}
ed[u]=dfn;
}
int LCA(int x,int y) {
int i,j;
if(dep[x]!=dep[y]) {
if(dep[x]>dep[y]) {
swap(x,y);
}
for(i=19;i>=0;--i) {
if(dep[fa[i][y]]>=dep[x]) {
y=fa[i][y];
}
}
}
if(x==y) {
return x;
}
for(i=19;i>=0;--i) {
if(fa[i][x]!=fa[i][y]) {
x=fa[i][x];
y=fa[i][y];
}
}
return fa[0][x];
}
int jump(int x,int d) {
for(int i=19;i>=0;--i) {
if(dep[fa[i][x]]>=d) {
x=fa[i][x];
}
}
return x;
}
void solve(int l,int r,int l1,int r1,int L,int R) {
if(l==r) {
for(int i=L;i<=R;++i) {
answer[as[i].id]=A[l];
}
return;
}
int mid=(l+r)>>1,cn1=0,s=0,cn2=0,as1=0,as2=0;
for(int i=l1;i<=r1;++i) {
if(t[i].val<=mid) {
tmp1[++cn1]=t[i]; // 是左面的
sg[++s]=Seg(t[i].x1,t[i].x2,t[i].y2,1);
sg[++s]=Seg(t[i].y1+1,t[i].x2,t[i].y2,-1);
}
else {
tmp2[++cn2]=t[i];
}
}
sort(sg+1,sg+1+s,cmp_seg);
int j=1;
for(int i=L;i<=R;++i) {
while(j<=s&&sg[j].x<=as[i].x) {
BIT::update(sg[j].l,sg[j].d);
BIT::update(sg[j].r+1,sg[j].d*-1);
++j;
}
int tmp=BIT::query(as[i].y);
if(tmp>=as[i].y) {
gl[++as1]=as[i];
}
else {
as[i].kth-=tmp;
gr[++as2]=as[i];
}
}
for(int i=1;i<=s;++i) {
BIT::clr(sg[i].l);
BIT::clr(sg[i].r+1);
}
int pos=l1;
for(int i=1;i<=cn1;++i) {
t[pos++]=tmp1[i];
}
for(int i=1;i<=cn2;++i) {
t[pos++]=tmp2[i];
}
pos=L;
for(int i=1;i<=as1;++i) {
as[pos++]=gl[i];
}
for(int i=1;i<=as2;++i) {
as[pos++]=gr[i];
}
solve(l,mid,l1,l1+cn1-1,L,L+as1-1);
solve(mid+1,r,l1+cn1,r1,L+as1,R);
}
int main() {
setIO("input");
int i,j,t1=0;
scanf("%d%d%d",&n,&P,&Q);
for(i=1;i<n;++i) {
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,0);
for(i=1;i<=P;++i) {
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
A[i]=c;
int lca=LCA(u,v);
if(lca!=u&&lca!=v) {
if(st[u]>st[v]) {
swap(u,v);
}
t[++t1]=data(st[u],ed[u],st[v],ed[v],c);
}
else {
if(lca==u) {
swap(u,v);
}
int w=jump(u,dep[v]+1);
t[++t1]=data(1,st[w]-1,st[u],ed[u],c);
t[++t1]=data(st[u],ed[u],ed[w]+1,n,c);
}
}
sort(A+1,A+1+P);
for(i=1;i<=t1;++i) {
t[i].val=lower_bound(A+1,A+1+P,t[i].val)-A;
}
for(i=1;i<=Q;++i) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(st[x]>st[y]) {
swap(x,y);
}
as[i]=qu(st[x],st[y],i,z);
}
sort(as+1,as+1+Q,cmp_qu);
solve(1,P,1,P,1,Q);
for(i=1;i<=Q;++i) {
printf("%d\n",answer[i]);
}
return 0;
}