2015 HNOI接水果问题二:解决方案解析
考虑水果 ( u , v ) (u,v) (u,v)包含盘子 ( x , y ) (x,y) (x,y)的条件,可以以 l c a lca lca分情况来讨论,规定 s t [ x ] st[x] st[x]为 x x x的 d f n dfn dfn序, e d [ x ] ed[x] ed[x]为 x x x子树内的最大的 d f n dfn dfn序(默认 s t [ u ] < s t [ v ] st[u]<st[v] st[u]<st[v], s t [ x ] < s t [ y ] st[x]<st[y] st[x]<st[y])。
第一种情况,
l
c
a
(
u
,
v
)
≠
u
lca(u,v)\not=u
lca(u,v)=u,那么
x
x
x在
u
u
u的子树内,
y
y
y在
v
v
v的子树内,也就是:
s
t
[
u
]
≤
s
t
[
x
]
≤
e
d
[
u
]
st[u]\leq st[x]\leq ed[u]
st[u]≤st[x]≤ed[u],并且
s
t
[
v
]
≤
s
t
[
y
]
≤
e
d
[
v
]
st[v]\leq st[y]\leq ed[v]
st[v]≤st[y]≤ed[v]
第二种情况,
l
c
a
(
u
,
v
)
=
u
lca(u,v)=u
lca(u,v)=u,那么
y
y
y在
v
v
v的子树内,找到
u
u
u在
v
v
v方向的第一个点
p
p
p,那么
x
x
x就在
[
1
,
s
t
[
p
]
−
1
]
[1,st[p]-1]
[1,st[p]−1]或者
[
e
d
[
p
]
+
1
,
n
]
[ed[p]+1,n]
[ed[p]+1,n],也就是:
1
≤
s
t
[
x
]
≤
s
t
[
p
]
−
1
1\leq st[x]\leq st[p]-1
1≤st[x]≤st[p]−1,
s
t
[
v
]
≤
s
t
[
y
]
≤
e
d
[
v
]
st[v]\leq st[y]\leq ed[v]
st[v]≤st[y]≤ed[v]或者
s
t
[
v
]
≤
s
t
[
x
]
≤
e
d
[
v
]
st[v]\leq st[x]\leq ed[v]
st[v]≤st[x]≤ed[v],
e
d
[
p
]
+
1
≤
s
t
[
y
]
≤
n
ed[p]+1\leq st[y]\leq n
ed[p]+1≤st[y]≤n
可以用整体二分,维护
[
q
l
,
q
r
]
[ql,qr]
[ql,qr]的问题答案为
[
l
,
r
]
[l,r]
[l,r],然后我们二分一个
m
i
d
mid
mid,把
[
l
,
m
i
d
]
[l,mid]
[l,mid]的修改和
[
q
l
,
q
r
]
[ql,qr]
[ql,qr]的询问都塞到一个数组里,然后按第一维排序,修改需要拆成两个,在左端点插入右段删除,第二维可以树状数组维护,询问考虑分到左边还是分到右边,就用K大数查询
类似的方法即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 100005;
int read()
{
int x=0,flag=1;char c;
while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*flag;
}
int n,m,q,tot,cnt,st[M],ed[M],f[M];
int fa[M][20],dep[M],ans[M],bit[M];
struct edge
{
int v,next;
edge(int V=0,int N=0) : v(V) , next(N) {}
}e[M];
struct node
{
int xl,xr,yl,yr,v;
bool operator < (node b) const
{
return v<b.v;
}
}pl[M];
struct query
{
int u,v,k,id;
}L[M],R[M],p[M];
struct data
{
int op,x,a,b,c;
bool operator < (data b) const
{
if(x==b.x) return op<b.op;
return x<b.x;
}
}a[2*M];
void dfs(int u,int p)
{
dep[u]=dep[p]+1;
st[u]=++cnt;fa[u][0]=p;
for(int i=1;i<20;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==p) continue;
dfs(v,u);
}
ed[u]=cnt;
}
int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--)
if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];
if(u==v) return u;
for(int i=19;i>=0;i--)
if(fa[u][i]^fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int up(int x,int dis)
{
for(int i=19;i>=0;i--)
if(dis&(1<<i))
x=fa[x][i];
return x;
}
int lowbit(int x)
{
return x&(-x);
}
void upd(int x,int f)
{
for(int i=x;i<=n;i+=lowbit(i))
bit[i]+=f;
}
int ask(int x)
{
int r=0;
for(int i=x;i>=1;i-=lowbit(i))
r+=bit[i];
return r;
}
void modify(int l,int r,int v)
{
upd(l,v);
upd(r+1,-v);
}
void cdq(int l,int r,int ql,int qr)
{
if(ql>qr || l>r) return ;
if(l==r)
{
for(int i=ql;i<=qr;i++)
ans[p[i].id]=pl[l].v;
return ;
}
int mid=(l+r)>>1,tl=0,tr=0,t=0;
for(int i=l;i<=mid;i++)
{
a[++t]=data{0,pl[i].xl,pl[i].yl,pl[i].yr,1};
a[++t]=data{2,pl[i].xr,pl[i].yl,pl[i].yr,-1};
}
for(int i=ql;i<=qr;i++)
a[++t]=data{1,p[i].u,p[i].v,i,0};
sort(a+1,a+1+t);
for(int i=1;i<=t;i++)
{
if(a[i].op!=1)
modify(a[i].a,a[i].b,a[i].c);
else
{
int tmp=ask(a[i].a),j=a[i].b;
if(tmp>=p[j].k) L[++tl]=p[j];
else p[j].k-=tmp,R[++tr]=p[j];
}
}
for(int i=1;i<=tl;i++) p[ql+i-1]=L[i];
for(int i=1;i<=tr;i++) p[ql+tl+i-1]=R[i];
cdq(l,mid,ql,ql+tl-1);
cdq(mid+1,r,ql+tl,qr);
}
int main()
{
n=read();m=read();q=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
e[++tot]=edge(v,f[u]),f[u]=tot;
e[++tot]=edge(u,f[v]),f[v]=tot;
}
dfs(1,0);cnt=0;
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),c=read();
if(st[u]>st[v]) swap(u,v);
int Lca=lca(u,v);
if(Lca!=u)
pl[++cnt]=node{st[u],ed[u],st[v],ed[v],c};
else
{
int son=up(v,dep[v]-dep[u]-1);
pl[++cnt]=node{1,st[son]-1,st[v],ed[v],c};
pl[++cnt]=node{st[v],ed[v],ed[son]+1,n,c};
}
}
sort(pl+1,pl+1+cnt);
for(int i=1;i<=q;i++)
{
int u=read(),v=read(),k=read();
if(st[u]>st[v]) swap(u,v);
p[i]=query{st[u],st[v],k,i};
}
cdq(1,cnt,1,q);
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
}