传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4009
思路：先给定一些路径，每个路径有一个权值。
题目要求的是对于一个路径，它的子路径中权值第k大的是多少
首先我们观察一个盘子(u,v)，它能接到哪些水果呢？
分情况：如果u!=lca(u,v)
那么水果的两端点(a,b)就在盘子两端点的子树中
用dfs序来表示，就是dfn[u]<=a<=last[u],dfn[v]<=b<=last[v]
last[i]表示i的子树的最大 dfn
如果u==lca(u,v)
这时稍微有一些区别，w表示u的儿子且是v的祖先的点，注意不是u
那么b还是在v子树中，a在除了w子树之外的所有点中
dfn[v]<=b<=last[v]，1<=a<=dfn[w]-1||last[w]+1<=a<=n
这时，盘子就成了一个或两个矩形，水果就是点
问题就是求覆盖一个点的矩形中权值第k大的权值是多少》
扫描线+整体二分就可以了
我们先将矩形按权值从小到大排序
然后对于一个点，如果[l,mid]中能覆盖这个点的矩形数不小于k，则说明答案在[l,mid]中
否则在[mid+1,r]，同时k减去覆盖的矩形数
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=80010,maxk=18;
using namespace std;
int n,m,q,cnt,fa[maxn][maxk],dfn[maxn],tim,last[maxn],dep[maxn],ans[maxn],sum[maxn];
int pre[maxn],now[maxn],son[maxn],tot;
struct Plate{int xd,xu,yd,yu,v;}plate[maxn];
struct Event{int x,yd,yu,v,id;}event[maxn];
struct Poi{int x,y,k,id;}poi[maxn],tmp1[maxn],tmp2[maxn];
bool operator <(Plate a,Plate b){return a.v<b.v;}
bool operator <(Event a,Event b){return a.x==b.x?a.id<b.id:a.x<b.x;}
void add(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
struct Bit{
int val[maxn];
void modify(int l,int r,int v){
for (int i=l;i<=n;i+=(i&(-i))) val[i]+=v;
for (int i=r+1;i<=n;i+=(i&(-i))) val[i]-=v;
}
int query(int x){int res=0;for (;x;x-=(x&(-x))) res+=val[x];return res;}
}T;
void dfs(int x){
dfn[x]=++tim;
for (int i=0;fa[x][i];i++) fa[x][i+1]=fa[fa[x][i]][i];
for (int y=now[x];y;y=pre[y]) if (son[y]!=fa[x][0])
fa[son[y]][0]=x,dep[son[y]]=dep[x]+1,dfs(son[y]);
last[x]=tim;
}
int jump(int a,int h){for (int i=16;h;i--) if (h>=(1<<i)) h-=(1<<i),a=fa[a][i];return a;}
int lca(int a,int b){
if (dep[a]<dep[b]) swap(a,b);
a=jump(a,dep[a]-dep[b]);
if (a==b) return a;
for (int i=16;i>=0;i--) if (fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i];
return fa[a][0];
}
void solve(int l,int r,int st,int ed){
if (st>ed) return;
if (l==r){
for (int i=st;i<=ed;i++) ans[poi[i].id]=plate[l].v;
return;
}
int mid=(l+r)>>1,siz=0;
for (int i=l;i<=mid;i++){
event[++siz]=(Event){plate[i].xd,plate[i].yd,plate[i].yu,1,0};
event[++siz]=(Event){plate[i].xu,plate[i].yd,plate[i].yu,-1,n+1};
}
for (int i=st;i<=ed;i++) event[++siz]=(Event){poi[i].x,poi[i].y,0,0,i};
sort(event+1,event+1+siz);
for (int i=1;i<=siz;i++)
if (st<=event[i].id&&event[i].id<=ed) sum[event[i].id]=T.query(event[i].yd);
else T.modify(event[i].yd,event[i].yu,event[i].v);
int a=0,b=0;
for (int i=st;i<=ed;i++)
if (sum[i]>=poi[i].k) tmp1[++a]=poi[i];
else tmp2[++b]=(Poi){poi[i].x,poi[i].y,poi[i].k-sum[i],poi[i].id};
for (int i=st;i<=st+a-1;i++) poi[i]=tmp1[i-st+1];
for (int i=st+a;i<=ed;i++) poi[i]=tmp2[i-st-a+1];
solve(l,mid,st,st+a-1),solve(mid+1,r,st+a,ed);
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for (int i=1,a,b;i<n;i++) scanf("%d%d",&a,&b),add(a,b),add(b,a);
dfs(1);
for (int i=1,a,b,c,u;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);u=lca(a,b);
if (dfn[a]>dfn[b]) swap(a,b);
if (u!=a) plate[++cnt]=(Plate){dfn[a],last[a],dfn[b],last[b],c};
else{
int w=jump(b,dep[b]-dep[a]-1);
plate[++cnt]=(Plate){1,dfn[w]-1,dfn[b],last[b],c};
if (last[w]<n) plate[++cnt]=(Plate){dfn[b],last[b],last[w]+1,n,c};
}
}
sort(plate+1,plate+1+cnt);
for (int i=1,a,b,k;i<=q;i++){
scanf("%d%d%d",&a,&b,&k);
if (dfn[a]>dfn[b]) swap(a,b);
poi[i]=(Poi){dfn[a],dfn[b],k,i};
}
solve(1,cnt,1,q);
for (int i=1;i<=q;i++) printf("%d
",ans[i]);
return 0;
}