洛谷P2056 [ZJOI2007]捉迷藏

题目描述

题解

听说是边分治板子题所以来补下坑。

其实第一眼看到题目我的想法是一条边只有当两端都是关闭的时候才是有效边，于是就可以线段树分治，然后用可持久化并查集维护直径，应该也是对的吧（没写不知道），but我是来补坑的。

所以来讲讲边分治是啥，就像点分治一样，是用来解决跟链有关的东西，区别就是边分治的每个节点是边。然后像点分治那样去解决即可，但如果一张图是菊花图的话会被卡，所以我们要重建一下图，大概就像下图这样把儿子分散开来。

这样整棵树就变成二叉的了，因此我们总能找到一条边使得这条边两侧的边的差不会超过 $1$ ，这样就能保证边分树层数是 $O(logn)$ 的。然后每次修改一个点的话就在边分树上跳即可。

对于这题来说我们可以在每条边上用堆维护左右子树内的点到这条边的最大距离即可，修改一次次数不会超过 $O(logn)$ ，故效率为 $O(Qlo{g}^{2}n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,hd[N],V[N],W[N],nx[N],sz[N],ax[N];
int ls[N],rs[N],t=1,o,rt,su,is[N],m,q;
char ch[3];bool vis[N];
vector<int>e[N];struct O{int u,d;};
bool operator < (O A,O B){return A.d<B.d;}
priority_queue<O>s[N][2];
struct P{int k,l,d;};vector<P>p[N];
void Add(int u,int v){e[u].push_back(v);}
void add(int u,int v,int w){nx[++t]=hd[u];V[hd[u]=t]=v;W[t]=w;
}
void rebuild(int u,int fr){int x=0,z=e[u].size();is[u]=1;for (int v,y,i=0;i<z;i++){if ((v=e[u][i])==fr) continue;if (!x) add(u,v,1),add(v,u,1),x=u;else y=++n,add(x,y,0),add(y,x,0),add(y,v,1),add(v,y,1),x=y;rebuild(v,u);}
}
void Sz(int u,int fr){sz[u]=1;for (int i=hd[u];i;i=nx[i])if (V[i]!=fr && !vis[i>>1])Sz(V[i],u),sz[u]+=sz[V[i]];
}
void Rt(int u,int fr){for (int i=hd[u],v;i;i=nx[i])if (V[i]!=fr && !vis[i>>1]){Rt(V[i],u);v=max(sz[V[i]],o-sz[V[i]]);if (v<su) rt=i,su=v;}
}
void find(int u,int fr,int d,int k,int l){if (is[u]) s[k][l].push((O){u,d}),p[u].push_back((P){k,l,d});for (int i=hd[u];i;i=nx[i])if (V[i]!=fr && !vis[i>>1])find(V[i],u,d+W[i],k,l);
}
void upd(int k){for (int i=0;i<2;i++)while(!s[k][i].empty() && !is[s[k][i].top().u]) s[k][i].pop();if (s[k][0].empty() || s[k][1].empty()) ax[k]=0;else ax[k]=s[k][0].top().d+s[k][1].top().d+W[k<<1];ax[k]=max(ax[k],max(ax[ls[k]],ax[rs[k]]));
}
int ediv(int u){Sz(u,0);o=sz[u];su=1e9;rt=0;Rt(u,0);if (!rt) return 0;int x=V[rt],y=V[rt^1],z=rt>>1;vis[z]=1;find(x,0,0,z,0);find(y,0,0,z,1);if (!t) t=z;ls[z]=ediv(x);rs[z]=ediv(y);upd(z);return z;
}
void setbl(int u){int z=p[u].size();for (int i=z-1;~i;i--){P v=p[u][i];s[v.k][v.l].push((O){u,v.d});upd(v.k);}
}
void setwh(int u){int z=p[u].size();for (int i=z-1;~i;i--) upd(p[u][i].k);
}
int main(){cin>>n;m=n;for (int u,v,i=1;i<n;i++)scanf("%d%d",&u,&v),Add(u,v),Add(v,u);rebuild(1,0);t=0;ediv(1);cin>>q;for (int x;q--;){scanf("%s",ch);if (ch[0]=='G'){if (!m) puts("-1");else if (m<2) puts("0");else printf("%d\n",ax[t]);}else{scanf("%d",&x);is[x]^=1;if (is[x]) m++,setbl(x);else m--,setwh(x);}}return 0;
}