Description:
给你一棵树和一个路径集合,每次询问某条给定路径包含的路径集合中第k大的路径的权值
Hint:
(n,mle 50000)
Solution:
毒瘤题
先考虑这个包含的条件怎么判断? 先把原树的dfn求出来
1.如果两点没有祖先关系,则显然所求路径的端点分别位于两点子树中
即: (dfn[a] le x le dfn[a]+sz[a]-1) (dfn[b] le y le dfn[b]+sz[b]-1)
2.如果有祖先关系,则路径一端不变,另一端除这棵子树内其他位置都合法
即 (dfn[a] le x le dfn[a]+sz[a]-1) (1 le y le dfn[b]+1 or dfn[b]+sz[b] le y le n)
把路径集合看成矩形
询问就是在求覆盖一个点的矩形中第k大的那个
考虑整体二分,把这些矩形按权值排序
每次递归时扫描线算出一个点被覆盖的次数,某时刻满足刚刚被覆盖k次,则找到答案
复杂度(O(nlog^2n))
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e5+5;
int n,m,q,z,pl,df,ct,cnt;
int c[mxn],hd[mxn],dfn[mxn],lst[mxn],dep[mxn],res[mxn],ans[mxn];
int f[mxn][18];
inline int read() {
char c=getchar(); int x=0,f=1;
while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
return x*f;
}
inline void chkmax(int &x,int y) {if(x<y) x=y;}
inline void chkmin(int &x,int y) {if(x>y) x=y;}
struct ed {
int to,nxt;
}e[mxn<<1];
inline void add(int u,int v) {
e[++ct]=(ed) {v,hd[u]}; hd[u]=ct;
}
struct P {
int x1,x2,y1,y2,val,id;
friend bool operator < (P a,P b) {
return a.val<b.val;
}
}plt[mxn];
struct T {
int x,l,r,val,id;
friend bool operator < (T a,T b) {
return a.x==b.x?a.id<b.id:a.x<b.x;
}
}t[mxn];
struct F {
int x,y,k,id;
}fr[mxn],tl[mxn],tr[mxn];
int lb(int x) {return x&-x;}
void mod(int l,int r,int y) {
++r;
while(l<=n) c[l]+=y,l+=lb(l);
while(r<=n) c[r]-=y,r+=lb(r);
}
int query(int x) {
int y=0;
while(x) y+=c[x],x-=lb(x);
return y;
}
int lca(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
for(int i=16;i>=0;--i)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y) return x;
for(int i=16;i>=0;--i)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
void dfs(int u,int fa) {
dfn[u]=++df; dep[u]=dep[fa]+1; f[u][0]=fa;
for(int i=hd[u];i;i=e[i].nxt) {
int v=e[i].to;
if(v==fa) continue ;
dfs(v,u);
}
lst[u]=df;
}
void solve(int l,int r,int ql,int qr) {
if(ql>qr) return ;
if(l==r) {
for(int i=ql;i<=qr;++i) ans[fr[i].id]=plt[l].val;
return ;
}
int mid=(l+r)>>1,tot=0,L=0,R=0;
for(int i=l;i<=mid;++i) {
t[++tot]=(T){plt[i].x1,plt[i].y1,plt[i].y2,1,0};
t[++tot]=(T){plt[i].x2,plt[i].y1,plt[i].y2,-1,n+1};
}
for(int i=ql;i<=qr;++i) t[++tot]=(T){fr[i].x,fr[i].y,0,0,i};
sort(t+1,t+tot+1);
for(int i=1;i<=tot;++i)
if(ql<=t[i].id&&t[i].id<=qr) res[t[i].id]=query(t[i].l);
else mod(t[i].l,t[i].r,t[i].val);
for(int i=ql;i<=qr;++i)
if(res[i]>=fr[i].k) tl[++L]=fr[i];
else tr[++R]=(F){fr[i].x,fr[i].y,fr[i].k-=res[i],fr[i].id};
for(int i=ql;i<=ql+L-1;++i) fr[i]=tl[i-ql+1];
for(int i=ql+L;i<=qr;++i) fr[i]=tr[i-ql-L+1];
solve(l,mid,ql,ql+L-1); solve(mid+1,r,ql+L,qr);
}
int main()
{
n=read(); m=read(); q=read(); int u,v,w,x,y;
for(int i=1;i<n;++i) {
u=read(); v=read();
add(u,v); add(v,u);
}
dfs(1,1);
for(int i=1;i<=n;++i)
for(int j=1;j<=16;++j)
f[i][j]=f[f[i][j-1]][j-1];
for(int i=1;i<=m;++i) {
u=read(); v=read(); w=read(); x=lca(u,v);
if(dfn[u]>dfn[v]) swap(u,v);
if(x!=u) plt[++cnt]=(P){dfn[u],lst[u],dfn[v],lst[v],w};
else {
x=dep[v]-dep[u]-1; y=v;
for(int i=16;i>=0;--i)
if(x>=(1<<i)) x-=(1<<i),y=f[y][i];
plt[++cnt]=(P){1,dfn[y]-1,dfn[v],lst[v],w};
if(lst[y]<n) plt[++cnt]=(P){dfn[v],lst[v],lst[y]+1,n,w}; //注意拆成的这两个矩形是没有交的,一个点只能被其中一个覆盖,所以这样不会错
}
}
sort(plt+1,plt+cnt+1);
for(int i=1;i<=q;++i) {
u=read(); v=read(); w=read();
if(dfn[u]>dfn[v]) swap(u,v);
fr[i]=(F){dfn[u],dfn[v],w,i};
}
solve(1,cnt,1,q);
for(int i=1;i<=q;++i) printf("%d
",ans[i]);
return 0;
}