P2056 [ZJOI2007]捉迷藏 （线段树分治做法）
simple_line · · 个人记录
- 首先概括下题意：维护树上的一个点集，支持删除和添加，求点集内的直径。
- 考虑没有删除操作如何维护。假设现在已经有了一个点集，然后向点集内加入一个点，显然会形成一些新的路径。一个朴素的维护方法就是，枚举每一条新路径，与当前直径比较，若更优就替换。如何优化这一个过程呢？给出一个结论，假设当前点集的直径的两个端点分别为x,y，那么新加入一个点，新形成的最长路径的另一个端点一定是x或者y（这个结论只在没有负边权时成立）。有了这个结论，维护点集就方便多了，我们只需要记录当前点集直径的两个端点，每次新加入点，就计算它与两个端点的距离，取更优的尝试更新当前直径。
- 现在加入删除操作。我们能以较为优秀的复杂度处理插入，但是不支持删除操作。每一个点都只对它存在的一段时间有贡献，考虑线段树分治，删除一个点就相当于在线段树上回溯。
- 代码如下
#include <bits/stdc++.h>
using namespace std;
const int N=6e5+9;
int head[N],nxt[N],go[N],sze,n,m;
char read_char(){
char ch=getchar();
while(ch!='G'&&ch!='C') ch=getchar();
return ch;
}
void add_edge(int u,int v){
++sze;nxt[sze]=head[u];head[u]=sze;go[sze]=v;
}
int dep[N],siz[N],son[N],top[N],fat[N],tot;
void dfs1(int id,int fa){
siz[id]=1;dep[id]=dep[fa]+1;fat[id]=fa;
for(int i=head[id];i;i=nxt[i]){
int to=go[i];
if(to==fa)continue;
dfs1(to,id);
siz[id]+=siz[to];
if(siz[to]>siz[son[id]]) son[id]=to;
}
}
void dfs2(int id,int fa){
if(son[id]){
top[son[id]]=top[id];
dfs2(son[id],id);
}
for(int i=head[id];i;i=nxt[i]){
int to=go[i];
if(to==fa||to==son[id]) continue;
top[to]=to;
dfs2(to,id);
}
}
int LCA(int x,int y){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
x=fat[fx];
fx=top[x];
}
if(dep[x]<dep[y]) return x;
else return y;
}
int cnt;
int hh[N<<2],nx[N*30],da[N*30],szz; //链表
int who[N]; //该时间有没有询问
int ans[N],pre[N]; //答案，上一次修改时间
void modefy(int id,int l,int r,int x,int y,int c){
if(x>y) return;
if(x<=l&&r<=y){
++szz;
nx[szz]=hh[id];
hh[id]=szz;
da[szz]=c;
return;
}
int mid=(l+r)>>1;
if(x<=mid) modefy(id<<1,l,mid,x,y,c);
if(mid<y) modefy(id<<1|1,mid+1,r,x,y,c);
}
void dfs(int id,int l,int r,int x,int y){
for(int i=hh[id];i;i=nx[i]){
int p=da[i];
if(!x) x=p;
else if(!y) y=p;
else{
int d1=dep[x]+dep[p]-2*dep[LCA(x,p)],
d2=dep[y]+dep[p]-2*dep[LCA(y,p)],
d3=dep[x]+dep[y]-2*dep[LCA(x,y)];
if(d1<d2){
swap(x,y);
swap(d1,d2);
}
if(d1>d3) y=p;
}
}
if(l==r){
if(who[l]){
if(!x) ans[who[l]]=-1;
else if(!y) ans[who[l]]=0;
else ans[who[l]]=dep[x]+dep[y]-2*dep[LCA(x,y)];
}
return;
}
int mid=(l+r)>>1;
dfs(id<<1,l,mid,x,y);
dfs(id<<1|1,mid+1,r,x,y);
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
dfs1(1,0);
top[1]=1;
dfs2(1,0);
scanf("%d",&m);
for(int i=1;i<=n;++i)
pre[i]=1;
for(int i=1;i<=m;++i){
char op=read_char();
if(op=='G'){
who[i]=++cnt;
}
else {
int x;scanf("%d",&x);
if(!pre[x]) pre[x]=i;
else {
modefy(1,1,m,pre[x],i-1,x);
pre[x]=0;
}
}
}
for(int i=1;i<=n;++i)
if(pre[i]) modefy(1,1,m,pre[i],m,i);
dfs(1,1,m,0,0);
for(int i=1;i<=cnt;++i)
printf("%d\n",ans[i]);
return 0;
}