https://www.lydsy.com/JudgeOnline/problem.php?id=4009
https://www.luogu.org/problemnew/show/P3242
因为预先做过LOJ6276：果树，不难想到对于树上路径的处理方法和它一样。
那么对于每个盘子用dfs序表示的路径点(u,v)，分两种情况：
1.u和v有一个不同于二者的lca
显然它能接到的水果的两端一个在u的子树中，一个在v的子树中。
2.v是u的祖先。
显然它能接到的水果的两端一个在u的子树中，一个在v的子树的补集（包括v）中。
那么对于一个水果的路径点，如果在这个矩形当中，就说明这个水果能够被哪些盘子所接。
那么处理完之后，显然不能用主席树来解决第k大（如果能当我没说），于是我们整体二分一下即可。
……这是我最开始做这道题的想法，但是码了4h后对此绝望，对着数据参着题解调到现在才过。
说几个（我）容易错的点：
1.区间第k小，所以不是第k大的做法，注意答案在左区间还是右区间。
2.用扫描线存的时候注意空间开大点，另外上边界不要忘了+1
3.矩形的x和y坐标以及水果的x和y坐标存法（顺序）一定要相同。
代码138行凑和吧，但是细节真心多。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=4e4+;
const int B=;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct path{
int to,nxt;
}e[N*];
struct dish{
int x1,x2,y,c,w;
}d[*N],td1[*N],td2[*N];
struct fruit{
int x,y,k,id;
}f[N],tf1[N],tf2[N];
int m,b[N],ans[N],tr[N],c[N];
int anc[N][B+],dep[N],size[N];
int n,p,q,cnt,head[N],pos[N],tot;
inline bool cmp1(dish a,dish b){
return a.y<b.y;
}
inline bool cmp2(fruit a,fruit b){
return a.y<b.y;
}
inline void add(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
void dfs(int u){
pos[u]=++tot;size[u]=;
dep[u]=dep[anc[u][]]+;
for(int i=;i<=B;++i)
anc[u][i]=anc[anc[u][i-]][i-];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v!=anc[u][]){
anc[v][]=u;
dfs(v);
size[u]+=size[v];
}
}
}
inline int LCA(int i,int j){
if(dep[i]<dep[j])swap(i,j);
for(int k=B;k>=;--k)
if(dep[anc[i][k]]>=dep[j])i=anc[i][k];
if(i==j)return i;
for(int k=B;k>=;--k)
if(anc[i][k]!=anc[j][k])
i=anc[i][k],j=anc[j][k];
return anc[i][];
}
inline int lowbit(int t){return t&(-t);}
inline void ins(int x,int y){
for(int i=x;i<=n;i+=lowbit(i))tr[i]+=y;
}
inline int qry(int x){
int res=;
for(int i=x;i;i-=lowbit(i))res+=tr[i];
return res;
}
inline void mdy(int l,int r,int w){
ins(l,w);ins(r+,-w);
}
void solve(int L,int R,int s,int t,int l,int r){
if(L>R||s>t)return;
if(l==r){
for(int i=L;i<=R;++i)ans[f[i].id]=c[l];
return;
}
int id1=,id2=,if1=,if2=,mid=(l+r)>>,j=s;
for(int i=L;i<=R;++i){
for(;j<=t&&d[j].y<=f[i].y;++j){
if(d[j].c>c[mid])td1[id1++]=d[j];
else mdy(d[j].x1,d[j].x2,d[j].w),td2[id2++]=d[j];
}
int tmp=qry(f[i].x);
if(f[i].k>tmp)f[i].k-=tmp,tf1[if1++]=f[i];
else tf2[if2++]=f[i];
}
for(;j<=t;++j){
if(d[j].c>c[mid])td1[id1++]=d[j];
else mdy(d[j].x1,d[j].x2,d[j].w),td2[id2++]=d[j];
}
int mdst=s+id1,MID=L+if1;
for(int i=s;i<mdst;++i)d[i]=td1[i-s];
for(int i=mdst;i<=t;++i)d[i]=td2[i-mdst];
for(int i=L;i<MID;++i)f[i]=tf1[i-L];
for(int i=MID;i<=R;++i)f[i]=tf2[i-MID];
solve(L,MID-,s,mdst-,mid+,r);solve(MID,R,mdst,t,l,mid);
return;
}
int main(){
n=read(),p=read(),q=read();
for(int i=;i<n;++i){
int u=read(),v=read();
add(u,v);add(v,u);
}
dfs();
for(int i=;i<=p;++i){
int u=read(),v=read();c[i]=read();
if(pos[u]>pos[v])swap(u,v);
int lca=LCA(u,v);
if(lca!=u&&lca!=v){
d[++m]=(dish){pos[u],pos[u]+size[u]-,pos[v],c[i],};
d[++m]=(dish){pos[u],pos[u]+size[u]-,pos[v]+size[v],c[i],-};
}else{
int t=v;
for(int k=B;k>=;--k)
if(dep[anc[t][k]]>=dep[u]+)t=anc[t][k];
d[++m]=(dish){,pos[t]-,pos[v],c[i],};
d[++m]=(dish){,pos[t]-,pos[v]+size[v],c[i],-};
d[++m]=(dish){pos[v],pos[v]+size[v]-,pos[t]+size[t],c[i],};
d[++m]=(dish){pos[v],pos[v]+size[v]-,n+,c[i],-};
}
}
for(int i=;i<=q;++i){
int u=read(),v=read(),k=read();
if(pos[u]>pos[v])swap(u,v);
f[i]=(fruit){pos[u],pos[v],k,i};
}
sort(d+,d+m+,cmp1);
sort(f+,f+q+,cmp2);
sort(c+,c+p+);
int len=unique(c+,c+p+)-c-;
solve(,q,,m,,len);
for(int i=;i<=q;++i)printf("%d\n",ans[i]);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++