Description
先给出一些盘子, 用路径x-y表示, 有权值
再有Q个询问, 表示水果, 用路径x-y表示
如果盘子是水果的子路径, 可以接住
对于每个水果, 输出可以接住它的盘子的第k小权
Solution
对于x-lca-y的盘子，水果一定一个在x子树，一个在y子树
对于x-lca的盘子，水果一定一个在x子树，一个在lca的非x子树，即dfn序中的两段区间
将一对区间(盘子)、一对点(水果)按dfn序顺序转化成一个矩形(盘子)和一个坐标(水果)
很明显就是整体二分了
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
using namespace std;
typedef long long LL;
const int M=40007;
inline int rd(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=0;
for(;isdigit(c);c=getchar())x=x*10+c-48;
return f?x:-x;
}
int n,m,Q;
int g[M];
struct edge{int y,next;}e[M<<1];
int top[M],pre[M],dep[M],sz[M],son[M];
int st[M],ed[M],pid[M];
struct pp{int d,id;}bb[M];
bool cd(pp x,pp y){return x.d<y.d;}
int val[M],tt;
struct plate{int x,y,z;}pan[M];
int nd[M],tmp[M],ans[M];
struct opr{
int x,y,z,kd;
opr(int xx=0,int yy=0,int zz=0,int kk=0){x=xx;y=yy;z=zz;kd=kk;}
}q[M*9],q1[M*9],q2[M*9],a[M*9];
int tot,ta;
bool dx(opr x,opr y){
if(x.x==y.x&&x.y==y.y) return x.kd<y.kd;
if(x.x==y.x) return x.y>y.y;
return x.x>y.x;
}
int c[M],col[M],T;
void addedge(int x,int y){
e[++tot].y=y;e[tot].next=g[x];g[x]=tot;
}
inline int lb(int x){return x&-x;}
void add(int x,int d){
for(;x>0;x-=lb(x)){
if(col[x]!=T){
col[x]=T;
c[x]=0;
}
c[x]+=d;
}
}
int get(int x){
int res=0;
for(;x<=n;x+=lb(x))
if(col[x]==T) res+=c[x];
return res;
}
void dfs1(int x){
sz[x]=1;
int p,y;
for(p=g[x];p;p=e[p].next)
if((y=e[p].y)!=pre[x]){
pre[y]=x;
dep[y]=dep[x]+1;
dfs1(y);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}
void dfs2(int x){
int p,y;
pid[st[x]=++T]=x;
if(son[x]){
top[son[x]]=top[x];
dfs2(son[x]);
}
for(p=g[x];p;p=e[p].next)
if((y=e[p].y)!=pre[x]&&y!=son[x]){
top[y]=y;
dfs2(y);
}
ed[x]=T;
}
int getlca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=pre[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
return x;
}
int jump(int x,int y){
while(dep[top[x]]>dep[y]){
x=top[x];
if(pre[x]==y) return x;
x=pre[x];
}
return pid[st[y]+1];
}
void addrectangle(int xx,int yy,int x,int y,int z){
q[++tot]=opr(xx-1,yy-1,z,1);
q[++tot]=opr(x,y,z,1);
q[++tot]=opr(xx-1,y,z,-1);
q[++tot]=opr(x,yy-1,z,-1);
}
void gao(){
int i;
sort(a+1,a+ta+1,dx);
for(T++,i=1;i<=ta;i++){
if(a[i].kd!=2) add(a[i].y,a[i].kd);
else tmp[a[i].z]+=get(a[i].y);
}
}
void solve(int l,int r,int L,int R){
if(l>r) return;
int i,j,t1=0,t2=0,mid=L+R>>1;
if(L==R){
for(i=l;i<=r;i++)
if(q[i].kd==2) ans[q[i].z]=val[L];
return;
}
ta=0;
for(i=l;i<=r;i++){
if(q[i].kd==2) a[++ta]=q[i],tmp[q[i].z]=0;
else if(q[i].z<=mid) a[++ta]=q[i];
}
gao();
for(i=l;i<=r;i++){
if(q[i].kd!=2){
if(q[i].z<=mid) q1[++t1]=q[i];
else q2[++t2]=q[i];
}
else{
if(nd[q[i].z]<=tmp[q[i].z]) q1[++t1]=q[i];
else{
nd[q[i].z]-=tmp[q[i].z];
tmp[q[i].z]=0;
q2[++t2]=q[i];
}
}
}
for(i=1;i<=t1;i++) q[l+i-1]=q1[i];
for(i=1;i<=t2;i++) q[l+t1+i-1]=q2[i];
solve(l,l+t1-1,L,mid);
solve(l+t1,r,mid+1,R);
}
int main(){
int i,x,y,xx,yy,z,lc;
n=rd(),m=rd(),Q=rd();
for(i=1;i<n;i++){
x=rd();
y=rd();
addedge(x,y);
addedge(y,x);
}
dep[1]=1;dfs1(1);top[1]=1;dfs2(1);
for(i=1;i<=m;i++){
pan[i].x=rd(),pan[i].y=rd();
bb[i].d=rd();bb[i].id=i;
}
sort(bb+1,bb+m+1,cd);bb[0].d=bb[1].d-1;
for(i=1;i<=m;i++){
if(bb[i].d!=bb[i-1].d) val[++tt]=bb[i].d;
pan[bb[i].id].z=tt;
}
for(i=1;i<=m;i++){
x=pan[i].x;
y=pan[i].y;
if(st[x]>st[y]) swap(x,y);
lc=getlca(x,y);
if(lc!=x&&lc!=y){
addrectangle(st[x],st[y],ed[x],ed[y],pan[i].z);
}
else{
if(lc!=x) swap(x,y);
lc=jump(y,x);
if(st[lc]>1) addrectangle(1,st[y],st[lc]-1,ed[y],pan[i].z);
if(ed[lc]<n) addrectangle(st[y],ed[lc]+1,ed[y],n,pan[i].z);
}
}
for(i=1;i<=Q;i++){
x=st[rd()],y=st[rd()];
if(x>y) swap(x,y);
nd[i]=rd();
q[++tot]=opr(x,y,i,2);
}
solve(1,tot,1,tt);
for(i=1;i<=Q;i++) printf("%d\n",ans[i]);
return 0;
}