bzoj1095 [ZJOI2007]Hide 捉迷藏（动态点分治|括号序列）

题目链接

题意：
树上黑白点，可以改变每个点的状态，求最远黑点对的距离

分析：
（之前接触过佳佳和岚的幸福生活，感觉这两口子的出镜率很高啊）

如果不改变每个点的状态，这道题就比较简单了：
1. 点分治
2. 树形dp：记录每个子树中黑点到子树根最远距离和次远距离（有点像树的直径），更新答案的时候用最大加上次大即可

有修改操作的点分治：动态点分治

树上的动态点分治就相当于序列上的线段树

首先我们需要构建一棵分治树：

我们在点分治的时候，每次找到子树中的重心
所以我们直接把各个重心按顺序连接起来，得到一棵分治树，ta的深度大概在 log $log$级别

像线段树一样，某个节点变化，只会导致分治树上的log个父亲的信息变化
对于每个父结点我们可以用某种数据结构来维护，使得修改的复杂度大概在 log $log$，修改一个点的复杂度就在 log2 $lo{g}^2$了

那么，如何建立这棵分治树呢?
其实和点分治几乎一模一样
只不过在点分治的时候，加上一句pre[u] = fa，就可以把这可分治树方便地建立出来

是不是蛮简单的？
然而这只是预处理第一步

构建可删堆（或者某种数据结构）

如果是静态的，对于每个点我们只需要知道ta作为重心时经过ta的两个黑点形成的最长链
如果是动态的话，点状态的改变会影响最长链的选取
所以我们需要将这些黑点到重心的信息记录下来，并维护最大值
对于这道题来说，堆其实是一个不错的选择。

堆一般可以用STL中的优先队列来代替（优点：空间用多少算多少）
但是优先队列有一个弊端就是不支持删除任意点，所以我们考虑怎么用两个堆实现动态删除的效果。

对于每个维护最大值的堆，再开一个删除堆，删除一个节点的时候我们将要删除的值放到删除堆中
每次取top的时候如果两个堆的堆顶元素是一样的就同时pop，直到两个堆的top不同或者删除堆为空，此时堆的堆顶就是真正的堆顶

维护信息

对于每个点维护两个堆，第一个堆C维护这个重心的子树中的点到父重心的距离
(注意是这个重心的父重心！)

第二个堆B维护这个重心的所有子重心中黑点的最大深度（也就是所有子重心的C堆堆顶）

最后用一个堆A维护所有重心B堆的最大值和次大值的和，A的堆顶就是答案
注意如果某个点是黑点，那么这个点的B堆中还要加入一个距离0，确保这个点和子树中的黑点可以形成合法的路径并更新答案

修改操作

把白点变黑点和黑点变白点分开考虑
先从C堆中更改，如果C堆的变化影响到了B堆，那么就修改B堆，B的变化影响到了A就修改A
反正是按照优先级的顺序修改即可

tip

这道题还有另一种解法：括号序列—>%%岛娘

代码真的不好写（也不好理解。。。orz）

#include<bits/stdc++.h>

using namespace std;

const int N=200005;
int st[N],tot=0,belong[N],pre[N][20],mi[20];
int n,m,root,sz,size[N],deep[N],f[N],Light;
bool vis[N],on[N];
struct node{
    int y,nxt;
};
node way[N<<1];

void add(int u,int w) {
    tot++;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
    tot++;way[tot].y=u;way[tot].nxt=st[w];st[w]=tot;
}

struct heap{
    priority_queue<int> h,d;
    void push(int x) {h.push(x);}     //添加堆
    void del(int x) {d.push(x);}      //删除堆
    void pop() {
        while (!d.empty()&&h.top()==d.top())
            h.pop(),d.pop();
        h.pop();
    } 
    int top() {
        while (!d.empty()&&h.top()==d.top())
            h.pop(),d.pop();
        if (!h.size()) return 0;
        return h.top();
    }
    int size() {
        return h.size()-d.size();
    }
    int secondtop() {               //查找第二大(不删除) 
        if (size()<2) return 0;
        int t=top(); pop();
        int t1=top(); 
        push(t);
        return t1;
    }
};
heap a,b[N],c[N];

void findroot(int now,int fa) {
    size[now]=1;
    f[now]=0;
    for (int i=st[now];i;i=way[i].nxt)
        if (way[i].y!=fa&&!vis[way[i].y]) {
            findroot(way[i].y,now);
            size[now]+=size[way[i].y];
            f[now]=max(f[now],size[way[i].y]);
        }
    f[now]=max(f[now],sz-size[now]);
    if (f[now]<f[root]) root=now;
}

void dfs(int now,int fa,int dep) {
    deep[now]=dep;
    pre[now][0]=fa;
    for (int i=1;i<=19;i++) {
        if (deep[now]-(1<<i)<0) break;
        pre[now][i]=pre[pre[now][i-1]][i-1];
    }
    for (int i=st[now];i;i=way[i].nxt)
        if (way[i].y!=fa)
            dfs(way[i].y,now,dep+1);
} 

int lca(int x,int y) {
    if (deep[x]<deep[y]) swap(x,y);
    int d=deep[x]-deep[y];
    if (d)
        for (int i=0;i<20&&d;i++,d>>=1)
            if (d&1)
                x=pre[x][i];
    if (x==y) return x;
    for (int i=19;i>=0;i--)
        if (pre[x][i]!=pre[y][i])
           x=pre[x][i],y=pre[y][i];
    return pre[x][0];
}

int dis(int x,int y) {
    return deep[x]+deep[y]-2*deep[lca(x,y)];
}

void solve(int now,int fa) {                    //构建分治树 
    belong[now]=fa;
    vis[now]=1;
    for (int i=st[now];i;i=way[i].nxt)
        if (!vis[way[i].y]) {
            sz=size[way[i].y]; root=0;
            findroot(way[i].y,now);
            solve(root,now);
        }
}

void Turn_off(int u,int w) {
    if (u==w) {
        b[u].push(0);          //关灯 
        if (b[u].size()==2) a.push(b[u].top());    //加入单链 
    }
    if (!belong[u]) return;
    int fa=belong[u],D=dis(fa,w),tmp=c[u].top();   //加入fa->u 
    c[u].push(D);
    if (D>tmp) {
        int mx=b[fa].top()+b[fa].secondtop(),siz=b[fa].size();
        if (tmp) b[fa].del(tmp);
        b[fa].push(D);
        int now=b[fa].top()+b[fa].secondtop();
        if (now>mx) {
            if (siz>=2) a.del(mx);
            if (b[fa].size()>=2) a.push(now);
        }
    }
    Turn_off(fa,w);
}

void Turn_on(int u,int w) {
    if (u==w) {
        if (b[u].size()==2) a.del(b[u].top());      //删除单链 
        b[u].del(0);
    }
    if (!belong[u]) return;
    int fa=belong[u],D=dis(fa,w),tmp=c[u].top();    //删除fa->u 
    c[u].del(D);
    if (D==tmp) {
        int mx=b[fa].top()+b[fa].secondtop(),siz=b[fa].size();
        b[fa].del(D);
        if (c[u].top()) b[fa].push(c[u].top());
        int now=b[fa].top()+b[fa].secondtop();
        if (now<mx) {
            if (siz>=2) a.del(mx);
            if (b[fa].size()>=2) a.push(now);
        }
    }
    Turn_on(fa,w);
}

int main() {
    scanf("%d",&n);
    Light=n;
    for (int i=1;i<=n;i++) on[i]=0;
    for (int i=1;i<n;i++) {
        int u,w;
        scanf("%d%d",&u,&w);
        add(u,w);
    }
    dfs(1,0,1);

    root=0; f[0]=N; sz=n;
    findroot(1,0);
    solve(root,0);

    for (int i=1;i<=n;i++) c[i].push(0);           //关灯 
    for (int i=1;i<=n;i++) Turn_off(i,i);

    scanf("%d",&m);
    while (m--) {
        char s[10];
        scanf("%s",s);
        if (s[0]=='G') {
            if (Light<=1) printf("%d\n",Light-1);
            else printf("%d\n",a.top());
        }
        else if (s[0]=='C') {
            int x;
            scanf("%d",&x);
            if (!on[x]) Turn_on(x,x),Light--;
            else Turn_off(x,x),Light++;
            on[x]^=1;
        }
    }
    return 0;
}