题意
内存限制：512 MiB
时间限制：6000 ms
风见幽香非常喜欢玩一个叫做 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$ 小的那个盘子，每个盘子可重复使用（没有使用次数的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水果路径的子路径）。幽香认为这个游戏很难，你能轻松解决给她看吗？
对于所有数据，$N,P,Q leq 40000$。
题解
考虑整体二分
把二分到的值 $leq mid$ 的盘子加入到某数据结构，然后对于该二分区间内的询问查询其被水果覆盖的盘子个数和 $k$ 的关系，再分左右区间
考虑如何处理一条路径被另一条路径覆盖问题
先求出其 $dfs$ 序，设 $L_u=dfn_u$ ，$R_u=dfn_u+sz_u-1$
将水果看成二维平面上的点 $(L_u,L_v)$
若要覆盖路径 $(x,y)$ 则应该：
1. $Lca(x,y) != x$
也就是 $L_x leq L_u leq R_x$，$L_y leq L_v leq R_y$
所以可以把 $(x,y)$ 看成矩形 $(L_x,L_y),(R_x,R_y)$
2. $Lca(x,y)=x$
设 $z$ 是 $x→y$ 上的第一个点，
那也就是满足一点在 $y$ 子树内，一点在 $z$ 子树外
即 $(1,L_y),(L_z-1,R_y)$ 和 $(R_z+1,L_y),(n,R_y)$
这样就是二维数点问题啦，用 $bit$ 处理即可
(矩形记得横纵坐标相反也算
代码
#include <bits/stdc++.h> #define I inline using namespace std; const int N=40005; int m,n,P,Q,V[N*2],nx[N*2],hd[N],t,f[N][17],d[N],in[N],tt,b[N],B,ans[N],ot[N],s[N]; struct O1{int x,l,r,w,v;}p[N*8],pp[N*8]; struct O2{int x,y,k,id;}q[N],qq[N]; I void add(int u,int v){V[++t]=v;nx[t]=hd[u];hd[u]=t;} I void dfs(int x,int fa){ f[x][0]=fa;d[x]=d[fa]+1;in[x]=++tt; for (int i=1;f[f[x][i-1]][i-1];i++) f[x][i]=f[f[x][i-1]][i-1]; for (int i=hd[x];i;i=nx[i]) if (V[i]!=fa) dfs(V[i],x);ot[x]=tt; } I int get(int x,int y){ int l=d[y]-d[x]-1; for (int i=16;~i;i--) if ((l>>i)&1) y=f[y][i]; return y; } I void ins(int X1,int Y1,int X2,int Y2,int w){ p[++m]=(O1){X1,X2,Y2,1,w},p[++m]=(O1){Y1+1,X2,Y2,-1,w}, p[++m]=(O1){X2,X1,Y1,1,w},p[++m]=(O1){Y2+1,X1,Y1,-1,w}; } I bool c1(O1 A,O1 B){return A.x<B.x;} I bool c2(O2 A,O2 B){return A.x<B.x;} I void update(int x,int v){for (;x<=n;x+=x&-x) s[x]+=v;} I int query(int x){int A=0;for (;x;x-=x&-x) A+=s[x];return A;} I void update(int l,int r,int v){update(l,v);update(r+1,-v);} I void solve(int l,int r,int pl,int pr,int ql,int qr){ if (l==r){ for (int i=ql;i<=qr;i++) ans[q[i].id]=b[l]; return; } int mid=(l+r)>>1,Pl=pl-1,Pr=pr+1,Ql=ql-1,Qr=qr+1,L; for (int k,j=pl,i=ql;i<=qr;i++){ while(j<=pr && p[j].x<=q[i].x){ if (p[j].v>b[mid]) pp[--Pr]=p[j]; else update(p[j].l,p[j].r,p[j].w), pp[++Pl]=p[j];j++; } k=query(q[i].y); if (q[i].k>k) q[i].k-=k,qq[--Qr]=q[i]; else qq[++Ql]=q[i]; if (i==qr) while(j<=pr){ if (p[j].v>b[mid]) pp[--Pr]=p[j]; else update(p[j].l,p[j].r,p[j].w),pp[++Pl]=p[j];j++; } } for (int j=pl;j<=pr;j++) if (p[j].v<=b[mid]) update(p[j].l,p[j].r,-p[j].w); L=pl-1;for (int i=pl;i<=Pl;i++) p[++L]=pp[i]; for (int i=pr;i>=Pr;i--) p[++L]=pp[i]; L=ql-1;for (int i=ql;i<=Ql;i++) q[++L]=qq[i]; for (int i=qr;i>=Qr;i--) q[++L]=qq[i]; if (pl<=Pl && ql<=Ql) solve(l,mid,pl,Pl,ql,Ql); if (Pr<=pr && Qr<=qr) solve(mid+1,r,Pr,pr,Qr,qr); } int main(){ scanf("%d%d%d",&n,&P,&Q); for (int x,y,i=1;i<n;i++) scanf("%d%d",&x,&y), add(x,y),add(y,x);dfs(1,0); for (int z,x,y,i=1;i<=P;i++){ scanf("%d%d%d",&x,&y,&b[i]); if (d[x]>d[y]) swap(x,y); if (in[x]<=in[y] && ot[x]>=ot[y]){ z=get(x,y); if (in[z]>1) ins(1,in[z]-1,in[y],ot[y],b[i]); if (ot[z]<n) ins(ot[z]+1,n,in[y],ot[y],b[i]); } else ins(in[x],ot[x],in[y],ot[y],b[i]); } sort(b+1,b+P+1);B=unique(b+1,b+P+1)-b-1; for (int x,y,i=1;i<=Q;i++) scanf("%d%d%d",&x,&y,&q[i].k), q[i].id=i,q[i].x=in[x],q[i].y=in[y]; sort(p+1,p+m+1,c1);sort(q+1,q+Q+1,c2); solve(1,B,1,m,1,Q); for (int i=1;i<=Q;i++) printf("%d ",ans[i]); return 0; }