浅谈树状数组与线段树：https://www.cnblogs.com/AKMer/p/9946944.html
题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=4009
把每个水果((u,v))转化成平面上的一个点((dfn[u],dfn[v]))。
我们考虑一个盘子，它可以接的水果的点集应该是矩形状的。
假设盘子的两个点是(u,v)：
1、当(u,v)的(lca)不是(u,v)之一时：
那么凡是在矩形((dfn[u],dfn[v],dfn[u]+siz[u]-1,dfn[v]+siz[v]-1))内的点都可以被这个盘子接住。
2、当(u,v)的(lca)是(u)或(v)时：
假设(lca)是(u)，(node)是(u)的儿子并且是(v)的祖先。那么这个时候存在两个矩阵：
((1,dfn[v],dfn[node]-1,dfn[v]+siz[v]-1))与((dfn[v],dfn[node]+siz[node],dfn[v]+siz[v]-1,n))
我们对于每个矩阵做扫描线，外层套一个值域线段树，然后把水果和盘子放在一起(sort)，动态修改然后在线段树上二分查找就行了。
时间复杂度：(O(nlog^2n))
空间复杂度：(O(nlog^2n))
代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int maxn=4e4+4;
int n,P,Q,tot,tim,cnt;
int now[maxn],pre[maxn*2],son[maxn*2];
int dep[maxn],dfn[maxn],siz[maxn],f[maxn][17];
int a[maxn],b[maxn],tmp[maxn],c[maxn],ans[maxn];
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
struct Project {
int x,y1,y2,k,opt;
Project() {}
Project(int _x,int _y1,int _y2,int _k,int _opt) {
x=_x,y1=_y1,y2=_y2,k=_k,opt=_opt;
}
bool operator<(const Project &a)const {
if(x==a.x)return (opt!=0)>(a.opt!=0);//当x相同时先修改
return x<a.x;
}
}p[maxn*3];
struct pos_segment_tree {
int tot;
int sum[maxn*175],ls[maxn*175],rs[maxn*175];
void change(int &p,int l,int r,int L,int R,int opt) {
if(!p)p=++tot;
if(L<=l&&r<=R) {sum[p]+=opt;return;}
int mid=(l+r)>>1;
if(R<=mid)change(ls[p],l,mid,L,R,opt);
else if(L>mid)change(rs[p],mid+1,r,L,R,opt);
else change(ls[p],l,mid,L,mid,opt),change(rs[p],mid+1,r,mid+1,R,opt);
}
int query(int p,int l,int r,int pos) {
if(l==r)return sum[p];
int mid=(l+r)>>1,res=sum[p];
if(pos<=mid)res+=query(ls[p],l,mid,pos);
else res+=query(rs[p],mid+1,r,pos);
return res;
}
}T_inside;
struct val_segment_tree {
int rt[maxn<<2];
void change(int p,int l,int r,int pos,int L,int R,int v) {
T_inside.change(rt[p],1,n,L,R,v);
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)change(p<<1,l,mid,pos,L,R,v);
else change(p<<1|1,mid+1,r,pos,L,R,v);
}
int query(int p,int l,int r,int pos,int rk) {
if(l==r)return tmp[l];
int mid=(l+r)>>1,tmp=T_inside.query(rt[p<<1],1,n,pos);
if(tmp>=rk)return query(p<<1,l,mid,pos,rk);
else return query(p<<1|1,mid+1,r,pos,rk-tmp);
}
}T_outside;
void add(int a,int b) {
pre[++tot]=now[a];
now[a]=tot,son[tot]=b;
}
void dfs(int fa,int u) {
dep[u]=dep[fa]+1,siz[u]=1;
f[u][0]=fa,dfn[u]=++tim;
for(int i=1;i<=16;i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(v!=fa)dfs(u,v),siz[u]+=siz[v];
}
pii lca(int u,int v) {
if(dep[u]<dep[v])swap(u,v);
for(int i=16;~i;i--)
if(dep[f[u][i]]>dep[v])
u=f[u][i];
if(f[u][0]==v)return make_pair(v,u);
if(dep[u]>dep[v])u=f[u][0];
for(int i=16;~i;i--)
if(f[u][i]!=f[v][i])
u=f[u][i],v=f[v][i];
return make_pair(f[u][0],0);
}
int main() {
n=read(),P=read(),Q=read();
for(int i=1;i<n;i++) {
int a=read(),b=read();
add(a,b),add(b,a);
}dfs(0,1);tot=Q;
for(int i=1;i<=P;i++)
a[i]=read(),b[i]=read(),tmp[i]=c[i]=read();
sort(tmp+1,tmp+P+1);
cnt=unique(tmp+1,tmp+P+1)-tmp-1;
for(int i=1;i<=P;i++)
c[i]=lower_bound(tmp+1,tmp+cnt+1,c[i])-tmp;
for(int i=1;i<=Q;i++) {
int a=read(),b=read();
a=dfn[a],b=dfn[b];
p[i].x=min(a,b);p[i].y1=max(a,b);
p[i].k=read(),p[i].y2=i;
}
for(int i=1;i<=P;i++) {
if(dep[a[i]]<dep[b[i]])swap(a[i],b[i]);
pii tmp=lca(a[i],b[i]);
int u=tmp.first,v=tmp.second;
int l=dfn[a[i]],r=dfn[a[i]]+siz[a[i]]-1;
if(u==b[i]) {
int L=1,R=dfn[v]-1;
if(L<=R) {
p[++tot]=Project(L,l,r,c[i],1);
p[++tot]=Project(R+1,l,r,c[i],-1);//R+1是因为要差分
}
L=dfn[v]+siz[v],R=n;
if(L<=R) {
p[++tot]=Project(l,L,R,c[i],1);
p[++tot]=Project(r+1,L,R,c[i],-1);
}
}
else {
int L=dfn[b[i]],R=dfn[b[i]]+siz[b[i]]-1;
if(r>R)swap(l,L),swap(r,R);
p[++tot]=Project(l,L,R,c[i],1);
p[++tot]=Project(r+1,L,R,c[i],-1);
}
}
sort(p+1,p+tot+1);
for(int i=1;i<=tot;i++) {
if(p[i].opt==0)ans[p[i].y2]=T_outside.query(1,1,cnt,p[i].y1,p[i].k);
else T_outside.change(1,1,cnt,p[i].k,p[i].y1,p[i].y2,p[i].opt);
}
for(int i=1;i<=Q;i++)
printf("%d
",ans[i]);
return 0;
}