[文章目录]
Description
有一个地图，是一棵由 n 个顶点、n-1 条边组成的树。这颗树上有 P 个盘子，每个盘子实际上是一条路径，并且每个盘子还有一个权值。第 i 个
盘子就是顶点a_i到顶点b_i的路径(由于是树，所以从a_i到b_i的路径是唯一的)，权值为c_i。接下来依次会有Q个水果掉下来，每个水果本质上也是一条路径，第i 个水果是从顶点 u_i 到顶点v_i 的路径。幽香每次需要选择一个盘子去接当前的水果：一个盘子能接住一个水果，当且仅当盘子的路径是水果的路径的子路径。
这里规定:从a 到b的路径与从b到 a的路径是同一条路径。
当然为了提高难度，对于第 i 个水果，你需要选择能接住它的所有盘子中，权值第 k_i 小的那个盘子，每个盘子可重复使用（没有使用次数的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水果路径的子路径）。N,P,Q<=40000 c<=10^9
整体二分，二分盘子权值的同时分治水果。
那么每一次分治我们需要找到左区间对应权值的所有路径被询问包含的个数。
预处理树的dfs序，那么一个路径a->b被包含有两种情况：
1.a,b无祖先关系：那么包含其路径的端点的dfs序的范围为a，b的子树dfs序的范围。
2.a为b的祖先：那么包含其路径的端点的dfs序范围为整个区间去掉a向b走的儿子的子树范围和b的子树的dfs序的范围。
将两个范围看做二维平面上的一个矩形，那么问题就变成给一堆矩形上的位置权值+1，查询单一位置权值。
差分矩形，离线扫描线。对于两个点dfs序正反对应的两种方式，发现两种dfs序范围不交，正反查询两次即可。时间复杂度
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 41000
int np,n,m;
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int in[N],out[N],dep[N],Log[N],fa[N][20],tim;
void dfs(int x,int pre)
{
for(int i=1;i<=Log[dep[x]];++i) fa[x][i]=fa[fa[x][i-1]][i-1];
in[x]=++tim;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
dep[to[i]]=dep[x]+1; fa[to[i]][0]=x;
dfs(to[i],x);
}
out[x]=tim;
}
struct node
{
int a,b,c,w;
}a[N];
bool cmp(node x,node y){return x.w<y.w;}
int cg[N],ans[N],t[N];
struct ques
{
int a,b,k;
}q[N];
struct cal
{
int x,y,w;
}ca[N*10];
int tca;
inline void add(int x1,int x2,int y1,int y2)
{
ca[++tca].x=x1; ca[tca].y=y1; ca[tca].w=1;
ca[++tca].x=x2+1; ca[tca].y=y1; ca[tca].w=-1;
ca[++tca].x=x1; ca[tca].y=y2+1; ca[tca].w=-1;
ca[++tca].x=x2+1; ca[tca].y=y2+1; ca[tca].w=1;
}
bool cmp1(cal x,cal y) {return x.x==y.x ? x.w<y.w : x.x<y.x;}
int f[N],c[N];
void BIT_fix(int x,int w){while(x<=tim) f[x]+=w,x+=-x&x;}
int BIT_query(int x){int re=0; while(x>0) re+=f[x],x-=-x&x; return re;}
void calc(int l,int r,int L,int R)
{
tca=0; int i;
for(i=l;i<=r;++i)
{
if(in[a[i].b]<=out[a[i].a])
{
add(in[a[i].b],out[a[i].b],1,in[a[i].c]-1);
add(in[a[i].b],out[a[i].b],out[a[i].c]+1,tim);
}
else add(in[a[i].b],out[a[i].b],in[a[i].a],out[a[i].a]);
}
for(i=L;i<=R;++i)
{
c[i]=0;
ca[++tca].x=in[q[cg[i]].a]; ca[tca].y=in[q[cg[i]].b]; ca[tca].w=i+1;
ca[++tca].x=in[q[cg[i]].b]; ca[tca].y=in[q[cg[i]].a]; ca[tca].w=i+1;
}
sort(ca+1,ca+tca+1,cmp1);
for(i=1;i<=tca;++i)
{
if(ca[i].w>1) c[ca[i].w-1]+=BIT_query(ca[i].y);
else BIT_fix(ca[i].y,ca[i].w);
}
for(i=1;i<=tca;++i) if(ca[i].w<=1) BIT_fix(ca[i].y,-ca[i].w);
}
void solve(int l,int r,int L,int R)
{
if(l==r)
{
for(int i=L;i<=R;++i) ans[cg[i]]=a[l].w;
return ;
}
int mid=(l+r)>>1,i1=L,i2=R,i;
calc(l,mid,L,R);
for(i=L;i<=R;++i)
{
if(q[cg[i]].k<=c[i]) t[i1++]=cg[i];
else q[cg[i]].k-=c[i],t[i2--]=cg[i];
}
for(i=L;i<=R;++i) cg[i]=t[i];
if(i2>=L) solve(l,mid,L,i2);
if(i1<=R) solve(mid+1,r,i1,R);
}
int main()
{
scanf("%d%d%d",&np,&n,&m);
int i,x,y;
for(i=2;i<=np;++i) Log[i]=Log[i>>1]+1;
for(i=1;i<np;++i)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
for(i=1;i<=n;++i)
{
scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].w);
if(in[a[i].a]>in[a[i].b]) swap(a[i].a,a[i].b);
if(in[a[i].b]<=out[a[i].a])
{
x=a[i].b;
for(int j=Log[dep[x]];j>=0;--j) if(dep[fa[x][j]]>dep[a[i].a]) x=fa[x][j];
a[i].c=x;
}
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=m;++i)
{
cg[i]=i, scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].k);
}
solve(1,n,1,m);
for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
return 0;
}