【ZJOI2007】bzoj1095 捉迷藏【解法二】

Description

　　捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩
捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋
子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的
时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要
求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两
个孩子的距离（即最远的两个关灯房间的距离）。 我们将以如下形式定义每一种操作： C(hange) i 改变第i个房
间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 G(ame) 开始一次游戏，查询最远的两个关灯房间的 距离。 Input

　　第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，
表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如 上文所示。 Output

　　对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关
着灯的，输出0；若所有房间的灯都开着，输出-1。

边分治做法见【这里】。
动态点分治，果然比边分治好写。
每个点维护两个堆$pq_1$和$pq_2$，$pq_1[u]$维护$u$的子树内所有节点到$fa[u]$的距离，$pq_2$维护所有儿子的$pq_1$的堆顶。再开一个$pq_3$维护所有点的$pq_2$的最大和次大值。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
void rd(int &x)
{x=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
}
void rdc(char &c)
{c=getchar();while (c<'A'||c>'Z') c=getchar();
}
struct heap
{priority_queue<int> pq,out;void ins(int x){pq.push(x);}void del(int x){out.push(x);}int top(){while (out.size()&&pq.top()==out.top()) pq.pop(),out.pop();return pq.top();}int twotop(){int x=top();del(x);int y=top();ins(x);return x+y;}int size(){return pq.size()-out.size();}
}pq1[100010],pq2[100010],pq3;
int fir[100010],ne[200010],to[200010],
out[100010],size[100010],clr[100010],
f[200010][20],dep[100010],pos[100010],log2[200010],
fa[100010],son_fir[100010],son_ne[100010],son_to[100010],
n,clo,R,son_num,root;
void add(int num,int u,int v)
{ne[num]=fir[u];fir[u]=num;to[num]=v;
}
void son_add(int u,int v)
{son_ne[++son_num]=son_fir[u];son_fir[u]=son_num;son_to[son_num]=v;fa[v]=u;
}
void init()
{rd(n);int u,v;for (int i=1;i<n;i++){scanf("%d%d",&u,&v);add(i*2,u,v);add(i*2+1,v,u);}
}
void dfs1(int u,int fa)
{int v;pos[u]=++clo;f[clo][0]=dep[u];for (int i=fir[u];i;i=ne[i])if ((v=to[i])!=fa){dep[v]=dep[u]+1;dfs1(v,u);f[++clo][0]=dep[u];}
}
void make_lca()
{dep[1]=1;dfs1(1,-1);for (int i=1;(1<<i)<=clo;i++) log2[1<<i]=i;for (int i=2;i<=clo;i++)if (!log2[i]) log2[i]=log2[i-1];for (int k=1;(1<<k)<=clo;k++)for (int i=1;i+(1<<k)-1<=clo;i++)f[i][k]=min(f[i][k-1],f[i+(1<<k-1)][k-1]);
}
int dis(int u,int v)
{if (u==v) return 0;int p=min(pos[u],pos[v]),q=max(pos[u],pos[v]),len=log2[q-p+1];return dep[u]+dep[v]-2*min(f[p][len],f[q-(1<<len)+1][len]);
}
void dfs3(int u,int fa,int siz)
{int v,maxs=-1;size[u]=1;for (int i=fir[u];i;i=ne[i])if (!out[v=to[i]]&&v!=fa){dfs3(v,u,siz);size[u]+=size[v];maxs=max(maxs,size[v]);}if (root==-1||max(maxs,siz-size[u])<max(maxs,siz-size[root])) root=u;
}
void dfs4(int u,int dis,int fa,int pos)
{int v;pq1[pos].ins(dis);for (int i=fir[u];i;i=ne[i])if (!out[v=to[i]]&&v!=fa)dfs4(v,dis+1,u,pos);
}
int dfs2(int u,int siz)
{int v,x,r1;root=-1;dfs3(u,-1,siz);r1=root;out[r1]=1;for (int i=fir[r1];i;i=ne[i])if (!out[v=to[i]]){x=dfs2(v,size[v]);son_add(r1,x);dfs4(v,1,-1,x);}for (int i=son_fir[r1];i;i=son_ne[i])pq2[r1].ins(pq1[son_to[i]].top());pq2[r1].ins(0);out[r1]=0;return r1;
}
void build()
{R=dfs2(1,n);for (int i=1;i<=n;i++)if (pq2[i].size()>=2)pq3.ins(pq2[i].twotop());
}
void modi(int u)
{clr[u]^=1;if (clr[u]){if (pq2[u].size()>=2) pq3.del(pq2[u].twotop());pq2[u].del(0);if (pq2[u].size()>=2) pq3.ins(pq2[u].twotop());for (int p=u;p!=R;p=fa[p]){if (pq2[fa[p]].size()>=2) pq3.del(pq2[fa[p]].twotop());if (pq1[p].size()) pq2[fa[p]].del(pq1[p].top());pq1[p].del(dis(u,fa[p]));if (pq1[p].size()) pq2[fa[p]].ins(pq1[p].top());if (pq2[fa[p]].size()>=2) pq3.ins(pq2[fa[p]].twotop());}}else{if (pq2[u].size()>=2) pq3.del(pq2[u].twotop());pq2[u].ins(0);if (pq2[u].size()>=2) pq3.ins(pq2[u].twotop());for (int p=u;p!=R;p=fa[p]){if (pq2[fa[p]].size()>=2) pq3.del(pq2[fa[p]].twotop());if (pq1[p].size()) pq2[fa[p]].del(pq1[p].top());pq1[p].ins(dis(u,fa[p]));if (pq1[p].size()) pq2[fa[p]].ins(pq1[p].top());if (pq2[fa[p]].size()>=2) pq3.ins(pq2[fa[p]].twotop());}}
}
void answer()
{int q,u,open=n;char c;rd(q);while (q--){rdc(c);if (c=='G'){if (open<2) printf("%d\n",open-1);else printf("%d\n",pq3.top());}else{rd(u);if (clr[u]) open++;else open--;modi(u);}}
}
int main()
{init();make_lca();build();answer();
}