![洛谷 P2056 [ZJOI2007]捉迷藏 题解【点分治】【堆】【图论】](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "洛谷 P2056 [ZJOI2007]捉迷藏 题解【点分治】【堆】【图论】")
动态点分治入 门 题？
题目描述
Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由 \(N\) 个屋子和 \(N-1\) 条双向走廊组成，这 \(N-1\) 条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这 \(N\) 个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。
我们将以如下形式定义每一种操作：
C(hange) i改变第 \(i\) 个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。G(ame)开始一次游戏，查询最远的两个关灯房间的距离。输入输出格式
输入格式：
第一行包含一个整数 \(N\)，表示房间的个数，房间将被编号为 \(1,2,3,\dots ,N\)的整数。
接下来 \(N-1\) 行每行两个整数 \(a,b\)，表示房间 \(a\) 与房间 \(b\) 之间有一条走廊相连。
接下来一行包含一个整数 \(Q\)，表示操作次数。接着 \(Q\) 行，每行一个操作，如上文所示。
输出格式：
对于每一个操作
Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出\(0\)；若所有房间的灯都开着，输出\(-1\)。输入输出样例
输入样例#1：
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G输出样例：
4
3
3
4说明
对于\(20\%\)的数据，\(N\le 50,M\le 100\)；
对于\(60\%\)的数据，\(N\le 3000,M\le 10000\)；
对于\(100\%\)的数据，\(N\le 100000,M\le 500000\)。
题解：
看起来动态点分治由于维护了一棵树高最多为 \(\log n\) 的点分树，每次修改操作的次数是 \(O(\log n)\)，但是处理父子关系还是很难维护的。
这个题第一眼看上去（如果不带修的话）是有点分治的思路在里面的。但是每次询问的图都在改变，因此就有了动态点分治。
由于我们需要找出树上最远的两个关灯的点，点的状态是动态的。而点分治每次都是在找重心，因此把每一次的重心分层，并两两“连边”，就形成了点分树。在点分树上的儿子所管辖的点数一定小于父亲所管辖的点数的一半，所以树高是 \(O(\log n)\)。
注：因此下文的“分治子树”指点分树上的子树。分治重心指分治子树的根节点。
点分治的核心是在子树重心处统计过重心的路径，而重点是不能在重心处统计同一子树内的答案。
本题要我们找最长关灯点对，因此我们需要找每个点 \(x\) 作为重心时的分治子树内到当前点 \(x\) 距离，并合并两个不同的子树中点的信息。由于只需要查询最大值，所以我们用一个堆来维护每一个分治子树中的信息。
又因为分治子树上的点到分治重心 \(k\) 的距离与当前点的距离不是线性关系（点 \(x\) 和点 \(k\) 不一定相邻，此时 \(x\to k\) 路径上的点就没有方便计算的途径），所以这个信息是子树 \(k\) 内的点到点 \(x\) 的距离。记最大值为 \(mx_k\)。
然后对于 \(x\) ，任意的 \(\left<x,y\right>\in \text{点分树}\) ，可以更新答案为\(\max_{\left<x,i\right>\in \text{点分树},\left<x,j\right>\in \text{点分树},i\ne j} mx_i+mx_j\)。此时我们发现，由于 \(i\ne j\) ，所以只需要取最大的两个 \(mx_k\) 就可以了。而这个信息也是动态的，所以应该再开一个堆。
此时我们每个点维护了两个堆
- 大根堆 \(\{q_x\}\) 维护以 \(x\) 为根的分治子树中到 \(fa_x\)（指 \(x\) 在分治子树上的父亲）的距离。
- 大根堆 \(\{q'_x\}\) 维护点分树上 \(x\) 的每个儿子 \(k\) 的 \(\max\{q_k\}\)。
接下来考虑如何开关灯。
我们每次只修改了一个点，并且一个点的信息只可能在它点分树上的祖先节点出现，有 \(O(\log n)\) 个，我们在构造点分树的时候可以预处理出每个点 \(x\) 到它第 \(i\) 个父亲的距离，记作 \(d_{i,x}\)，那个父亲记为 \(f_{i,x}\)，特殊地，每个点的直接父亲记为 \(fa_x\)。
此时考虑每次修改点 \(x\) 对第 \(i\) 个父亲的影响，看到上面两个堆的意义，还需要分类讨论。
- 当关灯时，\(u=f_{i,x}\) 子树中多了一个距离为 \(d_{i,x}\) 的关灯点。需要在 \(\{q_u\}\) 中插入 \(d_{i+1,x}\)。看是否 \(d_{i+1,x}\) 成为了 \(\{q_u\}\) 中最大的元素，如果是，则把 \(\{q'_{fa_u}\}\) 中原来的 \(u\) 答案删掉，更新为这个答案。
- 当开灯时，\(u\) 的子树中少了一个距离为 \(d_{i,x}\) 的关灯点，则需要在 \(\{q_u\}\) 中删除相应的元素，如果删除了最大的，再拿此时最大的补上去。
这时需要统计答案了。发现答案是 \(\max_{i=1}^n\max\{q'_i\}\) ，仍然是类似的堆操作。至此我们整道题维护了3种堆，届时输出最后一种堆的堆顶即可。
当子树内只有一个或没有关灯点的时候贡献都是 \(0\)，要输出 \(-1\) 的情况可以在外面判。一个点的时候还要存一下答案是否在最后一种堆中…因此边界情况会比较多。堆的删除是用懒惰删除法，@Dew 教了我一种神仙的结构体写法非常赞。
其他：注意 \(x,y\) 分别指父子的时候不要搞混了…
点分治+堆所以时间复杂度为 \(O((n+m)\log^2n)\)。
Code：
#include<cstdio>
#include<cstring>
#include<queue>
using std::priority_queue;
int read()
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
struct edge
{
int n,nxt;
edge(int n,int nxt)
{
this->n=n;
this->nxt=nxt;
}
edge(){}
}e[200000];
int head[100100],ecnt=-1;
void add(int from,int to)
{
e[++ecnt]=edge(to,head[from]);
head[from]=ecnt;
e[++ecnt]=edge(from,head[to]);
head[to]=ecnt;
}
bool used[100100];
int fa[100100],f[100100],rt,tot=0;
int sz[100100];
void dfs(int x,int from)
{
sz[x]=1;
f[x]=0;
for(int i=head[x];~i;i=e[i].nxt)
if(e[i].n!=from&&!used[e[i].n])
{
dfs(e[i].n,x);
sz[x]+=sz[e[i].n];
f[x]=f[x]>sz[e[i].n]?f[x]:sz[e[i].n];
}
f[x]=f[x]>tot-sz[x]?f[x]:tot-sz[x];
rt=f[x]<f[rt]?x:rt;
}
int d[18][100100],cnt[100100],dpt=1;
void Dfs(int x,int from)
{
d[++cnt[x]][x]=dpt;
++dpt;
for(int i=head[x];~i;i=e[i].nxt)
if(e[i].n!=from&&!used[e[i].n])
Dfs(e[i].n,x);
--dpt;
}
void divide(int x,int from)//仅初始化块
{
rt=0;
tot=sz[x];
dfs(x,x);
used[x=rt]=1;
fa[x]=from;
for(int i=head[x];~i;i=e[i].nxt)
if(!used[e[i].n])
divide(e[i].n,x);
for(int i=head[x];~i;i=e[i].nxt)
if(!used[e[i].n])
Dfs(e[i].n,x);
used[x]=0;
}
bool col[100100];
int sum=0;
struct heap
{
priority_queue<int> q;
priority_queue<int> p;
void maintain()
{
while(!p.empty()&&p.top()==q.top())
{
p.pop();
q.pop();
}
}
inline void POP(int x)
{p.push(x);}
inline void PUSH(int x)
{q.push(x);}
int TOP()
{
maintain();
return q.top();
}
inline int sz()
{return (q.size()-p.size());}
}q[100100],q_[100100],Q;
//q表示来源于自己子树中的
//q_表示存它爹的
int ans[100100];
bool gg[100100];
void upd(int x)
{
if(q[x].sz()==1)
{
if(!gg[x])
Q.POP(ans[x]);
ans[x]=q[x].TOP();
gg[x]=1;
}
else if(!q[x].sz())
{
if(!gg[x])
Q.POP(ans[x]);
gg[x]=0;
ans[x]=0;
Q.PUSH(0);
}
else
{
if(!gg[x])
Q.POP(ans[x]);
gg[x]=0;
int g=q[x].TOP();
q[x].POP(g);
ans[x]=g+q[x].TOP();
q[x].PUSH(g);
Q.PUSH(ans[x]);
}
}
void change(int x)
{
int y=x,tmp=0;
if(col[x])
{
col[x]=0;
--sum;
while(fa[y])
{
++tmp;
//先考虑y对fa[y]的原贡献
if(q_[y].TOP()==d[tmp][x])
{
q_[y].POP(d[tmp][x]);
//要删除一些元素了
q[fa[y]].POP(d[tmp][x]);
if(q_[y].sz())
q[fa[y]].PUSH(q_[y].TOP());
upd(fa[y]);
}
else
q_[y].POP(d[tmp][x]);
y=fa[y];
}
q[x].POP(0);
upd(x);
}
else
{
col[x]=1;
++sum;
q[x].PUSH(0);
upd(x);
while(fa[y])
{
++tmp;
if(!q_[y].sz()||d[tmp][x]>q_[y].TOP())
{
if(q_[y].sz())
q[fa[y]].POP(q_[y].TOP());
q[fa[y]].PUSH(d[tmp][x]);
upd(fa[y]);
}
q_[y].PUSH(d[tmp][x]);
y=fa[y];
}
}
}
int main()
{
memset(head,-1,sizeof(head));
f[0]=1e9;
int n,u,v;
n=read();
for(int i=1;i<n;++i)
{
u=read();
v=read();
add(u,v);
}
sz[1]=n;
divide(1,0);
for(int i=1;i<=n;++i)
Q.PUSH(0);
for(int i=1;i<=n;++i)
change(i);
char s[100];
int m;
m=read();
while(m--)
{
scanf("%s",s);
if(s[0]=='G')
{
if(!sum)
puts("-1");
else if(sum==1)
puts("0");
else
printf("%d\n",Q.TOP());
}
else
{
u=read();
change(u);
}
}
return 0;
}