题解 CF1464F【My Beautiful Madness】
whiteqwq
·
·
题解
CF1464F My Beautiful Madness解题报告：
更好的阅读体验
题意
给定一个 n 个结点的树，你需要维护一个路径的可重集。一共会进行 m 次操作，每次支持加入/删除一条路径，或者是查询可重集内所有路径的 d 邻域是否有交。
## 分析
性质题。
直接求交信息过于复杂，考虑找到一个点满足其包含在交内的概率必然最高。
我们发现这个点是所有路径的 $\text{lca}$ 最深点的 $d$ 级祖先（设其为 $p$），如果 $p$ 不在某条路径的 $d$ 邻域中的话，那么 $\text{lca}$ 最深的路径的 $d$ 邻域一定与这条路径无交。
于是我们用一个 $\text{multiset}$ 维护一下这个位置，考虑怎么判断它是否在交中。
我们取出 $p$ 的 $d$ 级祖先 $q$，那么在 $q$ 子树外的路径一定不包含 $p$，我们用一个树状数组维护一下树上差分就可以了。
在 $q$ 内的路径最靠近 $p$ 的位置一定是它的 $\text{lca}$，于是我们维护一下子树内当前所有关键点的直径就好了。
时间复杂度 $O((n+q)\log n)$。
## 代码
注意细节，实际上代码还是比较容易实现的。
```cpp
#include<stdio.h>
#include<vector>
#include<set>
#define lc(x) (x)<<1
#define rc(x) (x)<<1|1
#define lowbit(x) x&(-x)
#define inf 1000000000
using namespace std;
const int maxn=200005,maxt=maxn<<2,maxk=21;
int n,m,euls,dfns;
int st[maxn<<1][maxk],eul[maxn],lg[maxn<<1],dep[maxn],L[maxn],R[maxn],tt[maxn],fore[maxn][maxk],cnt[maxn];
vector<int>v[maxn];
multiset< pair<int,int> >s;
void dfs(int x,int last){
eul[x]=++euls,st[euls][0]=x,L[x]=++dfns;
dep[x]=dep[last]+1,fore[x][0]=last;
for(int i=1;i<=20;i++)
fore[x][i]=fore[fore[x][i-1]][i-1];
for(int i=0;i<v[x].size();i++)
if(v[x][i]!=last)
dfs(v[x][i],x),st[++euls][0]=x;
R[x]=dfns;
}
inline int calc(int a,int b){
return dep[a]<dep[b]? a:b;
}
inline int lca(int a,int b){
a=eul[a],b=eul[b];
if(a>b)
swap(a,b);
int k=lg[b-a+1];
return calc(st[a][k],st[b-(1<<k)+1][k]);
}
inline int dis(int a,int b){
if(a==-1||b==-1)
return -inf;
int c=lca(a,b);
return dep[a]+dep[b]-2*dep[c];
}
int getkth(int x,int k){
for(int i=0;i<=20&&x!=1;i++)
if((k>>i)&1)
x=fore[x][i];
return x;
}
void tupdate(int x,int v){
for(int i=x;i<=n;i+=lowbit(i))
tt[i]+=v;
}
int tquery(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))
res+=tt[i];
return res;
}
struct node{
int x,y,len;
}t[maxt];
node merge(node p,node q){
if(p.x==-1)
return q;
if(q.x==-1)
return p;
node res=p.len>q.len? p:q;
int a=dis(p.x,q.x),b=dis(p.x,q.y),c=dis(p.y,q.x),d=dis(p.y,q.y);
if(a>res.len)
res=node{p.x,q.x,a};
if(b>res.len)
res=node{p.x,q.y,b};
if(c>res.len)
res=node{p.y,q.x,c};
if(d>res.len)
res=node{p.y,q.y,d};
return res;
}
inline void pushup(int now){
t[now]=merge(t[lc(now)],t[rc(now)]);
}
void build(int l,int r,int now){
t[now]=node{-1,-1,-inf};
if(l==r)
return ;
int mid=(l+r)>>1;
build(l,mid,lc(now)),build(mid+1,r,rc(now));
}
void modify(int l,int r,int now,int p,int x,int w){
if(l==r){
if(w==1)
t[now]=node{x,x,0};
if(w==0)
t[now]=node{-1,-1,-inf};
return ;
}
int mid=(l+r)>>1;
if(p<=mid)
modify(l,mid,lc(now),p,x,w);
else modify(mid+1,r,rc(now),p,x,w);
pushup(now);
}
node query(int l,int r,int now,int L,int R){
if(L<=l&&r<=R)
return t[now];
int mid=(l+r)>>1;
if(L<=mid&&mid<R)
return merge(query(l,mid,lc(now),L,R),query(mid+1,r,rc(now),L,R));
if(L<=mid)
return query(l,mid,lc(now),L,R);
return query(mid+1,r,rc(now),L,R);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y),v[y].push_back(x);
}
dfs(1,1);
lg[0]=-1;
for(int i=1;i<=euls;i++)
lg[i]=lg[i>>1]+1;
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=euls;j++)
st[j][i]=calc(st[j][i-1],st[j+(1<<(i-1))][i-1]);
build(1,n,1);
while(m--){
int t,x,y,z;
scanf("%d%d",&t,&x);
if(t==1){
scanf("%d",&y),z=lca(x,y);
tupdate(L[x],1),tupdate(L[y],1),tupdate(L[z],-1);
s.insert(make_pair(dep[z],z));
if(cnt[z]==0)
modify(1,n,1,L[z],z,1);
cnt[z]++;
}
if(t==2){
scanf("%d",&y),z=lca(x,y);
tupdate(L[x],-1),tupdate(L[y],-1),tupdate(L[z],1);
s.erase(s.lower_bound(make_pair(dep[z],z)));
cnt[z]--;
if(cnt[z]==0)
modify(1,n,1,L[z],z,0);
}
if(t==3){
y=getkth(s.rbegin()->second,x),z=getkth(y,x);
if(tquery(R[z])-tquery(L[z]-1)!=s.size()){
puts("No");
continue;
}
node res=query(1,n,1,L[z],R[z]);
puts((dis(y,res.x)<=x&&dis(y,res.y)<=x)? "Yes":"No");
}
}
return 0;
}
```