Description
风见幽香非常喜欢玩一个叫做 osu!的游戏，其中她最喜欢玩的模式就是接水果。
由于她已经DT FC 了The big black, 她觉得这个游戏太简单了，于是发明了一个更加难的版本。首先有一个地图，是一棵由 n 个顶点、n-1 条边组成的树（例如图 1给出的树包含 8 个顶点、7 条边）。这颗树上有 P 个盘子，每个盘子实际上是一条路径（例如图 1 中顶点 6 到顶点 8 的路径），并且每个盘子还有一个权值。第 i 个盘子就是顶点a_i到顶点b_i的路径(由于是树，所以从a_i到b_i的路径是唯一的)，权值为c_i。接下来依次会有Q个水果掉下来，每个水果本质上也是一条路径，第i 个水果是从顶点 u_i 到顶点v_i 的路径。幽香每次需要选择一个盘子去接当前的水果：一个盘子能接住一个水果，当且仅当盘子的路径是水果的路径的子路径（例如图1中从 3到7 的路径是从1到8的路径的子路径）。这里规定:从a 到b的路径与从b到 a的路径是同一条路径。当然为了提高难度，对于第 i 个水果，你需要选择能接住它的所有盘子中，权值第 k_i 小的那个盘子，每个盘子可重复使用（没有使用次数的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水果路径的子路径）。幽香认为这个游戏很难，你能轻松解决给她看吗？
Input
第一行三个数 n和P 和Q，表示树的大小和盘子的个数和水果的个数。
接下来n-1 行，每行两个数 a、b，表示树上的a和b 之间有一条边。树中顶点
按1到 n标号。 接下来 P 行，每行三个数 a、b、c，表示路径为 a 到 b、权值为 c 的盘子，其
中0≤c≤10^9，a不等于b。
接下来Q行，每行三个数 u、v、k，表示路径为 u到 v的水果，其中 u不等于v，你需要选择第 k小的盘子，
第k 小一定存在。
Output
对于每个果子，输出一行表示选择的盘子的权值。
Solution
超级码农题，，写了我一下午。。
考虑盘子能影响到的水果构成了一个二维约束：
- 若(lca)不是两点中任意一个，则两个点的子树分别是两维约束。
- 否则全集减去(lca)的子树为第一维约束，剩下那个点的子树为第二维约束
这两维约束形成了若干个矩阵，而水果则可以看做是平面上的一个点。
那么做法就很显然了：
用扫描线把两维变一维，然后类似k大数查询那样维护扫描线那一维，对于水果按(x)坐标(sort)一遍顺便求出答案就好了。
注意对于一个矩阵，其实两维反过来也会被它影响到，所以对于每一个矩阵把它和(y=x)对称的矩阵也加进去。
内层线段树记得标记永久化，不然稳炸。
剩下细节问题自己考虑
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
const int maxn = 1e5+10;
int dfn[maxn],n,m,q,f[maxn][20],dep[maxn],sz[maxn];
struct Input_Tree {
int head[maxn],tot,dfn_cnt;
struct edge{int to,nxt;}e[maxn<<1];
void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
void ins(int u,int v) {add(u,v),add(v,u);}
void dfs(int x,int fa) {
f[x][0]=fa,dep[x]=dep[fa]+1,dfn[x]=++dfn_cnt,sz[x]=1;
for(int i=1;i<=16;i++) f[x][i]=f[f[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].nxt)
if(e[i].to!=fa) dfs(e[i].to,x),sz[x]+=sz[e[i].to];
}
int lca(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
for(int i=16;~i;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
for(int i=16;~i;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
}T;
int cnt,inx[maxn],iny[maxn],inz[maxn];
struct query {
int x,y,k,ans,id;
bool operator < (const query &rhs) const {return x<rhs.x;}
}a[maxn];
int cmp(query A,query b) {return A.id<b.id;}
int ls[maxn*200],rs[maxn*200],sum[maxn*200],tag[maxn*200],seg;
#define mid ((l+r)>>1)
struct Pos_Seg_Tree {
int rt;
void modify(int &p,int l,int r,int x,int y,int z) {
if(!p) p=++seg;
if(x<=l&&r<=y) return sum[p]+=z,void();
if(x<=mid) modify(ls[p],l,mid,x,y,z);
if(y>mid) modify(rs[p],mid+1,r,x,y,z);
}
int query(int p,int l,int r,int x) {
if(!p) return 0;
if(l==r) return sum[p];
if(x<=mid) return query(ls[p],l,mid,x)+sum[p];
else return query(rs[p],mid+1,r,x)+sum[p];
}
};
#define ls p<<1
#define rs p<<1|1
struct Val_Seg_Tree {
Pos_Seg_Tree t[maxn<<2];
void modify(int p,int l,int r,int x,int A,int b,int op) {
t[p].modify(t[p].rt,1,n,A,b,op);
if(l==r) return ;
if(x<=mid) modify(ls,l,mid,x,A,b,op);
else modify(rs,mid+1,r,x,A,b,op);
}
int query(int p,int l,int r,int x,int k) {
if(l==r) return l;
int s=t[ls].query(t[ls].rt,1,n,x);
if(s>=k) return query(ls,l,mid,x,k);
else return query(rs,mid+1,r,x,k-s);
}
}SGT;
#undef ls
#undef rs
#undef mid
struct line {
int up,down,val,op,x;
bool operator < (const line &rhs) const {return x<rhs.x;}
}l[maxn*20];
int r[maxn];
int main() {
read(n),read(m),read(q);
for(int i=1,x,y;i<n;i++) read(x),read(y),T.ins(x,y);
T.dfs(1,0);
for(int i=1;i<=m;i++) read(inx[i]),read(iny[i]),read(inz[i]),r[i]=inz[i];
sort(r+1,r+m+1);int M=unique(r+1,r+m+1)-r-1;
for(int i=1;i<=m;i++) inz[i]=lower_bound(r+1,r+M+1,inz[i])-r;
for(int i=1;i<=m;i++) {
int x=inx[i],y=iny[i],z=inz[i];
int t=T.lca(x,y);if(dep[x]>dep[y]) swap(x,y);
if(x==t) {
int son=y;
for(int j=16;~j;j--) if(dep[f[son][j]]>dep[x]) son=f[son][j];
l[++cnt]=(line){dfn[son]-1,1,z,1,dfn[y]};
l[++cnt]=(line){dfn[son]-1,1,z,-1,dfn[y]+sz[y]-1};
if(dfn[son]+sz[son]<=n) {
l[++cnt]=(line){n,dfn[son]+sz[son],z,1,dfn[y]};
l[++cnt]=(line){n,dfn[son]+sz[son],z,-1,dfn[y]+sz[y]-1};
}
} else {
if(dfn[x]>dfn[y]) swap(x,y);
l[++cnt]=(line){dfn[x]+sz[x]-1,dfn[x],z,1,dfn[y]};
l[++cnt]=(line){dfn[x]+sz[x]-1,dfn[x],z,-1,dfn[y]+sz[y]-1};
}
}
int c=cnt;
for(int i=1;i<=c;i+=2) {
int ldy=l[i].down,ldx=l[i].x,rux=l[i+1].x,ruy=l[i+1].up;
swap(ldx,ldy),swap(rux,ruy);
l[++cnt]=(line){ruy,ldy,l[i].val,1,ldx};
l[++cnt]=(line){ruy,ldy,l[i].val,-1,rux};
}
for(int i=1;i<=cnt;i++) if(l[i].op==-1) l[i].x++;
sort(l+1,l+cnt+1);
for(int i=1;i<=q;i++) {
read(a[i].x),read(a[i].y),read(a[i].k);a[i].id=i;
a[i].x=dfn[a[i].x],a[i].y=dfn[a[i].y];
}
sort(a+1,a+q+1);
int p=1;
for(int i=1;i<=cnt;i++) {
while(l[i].x>a[p].x&&p<=q) a[p].ans=SGT.query(1,1,n,a[p].y,a[p].k),p++;
SGT.modify(1,1,n,l[i].val,l[i].down,l[i].up,l[i].op);
}
sort(a+1,a+q+1,cmp);
for(int i=1;i<=q;i++) write(r[a[i].ans]);
return 0;
}