bzoj1095：Hide 捉迷藏（动态树分治）

我月考时一直在想动态树分治是个什么东西，直到看了这题题解才有点懂。

题面

题意：给出一棵黑白树，每次翻转一个点的颜色，或询问两个黑点间的最远距离。

由于是点对问题，可以想点分治。先考虑问题的静态版本，怎么用点分治求最远两个黑点的距离。

显然，对于一个重心，我们要知道每个连通块中，距离它最远的点的距离，前二大的加起来可以更新答案。

根据点分治的划分过程，每个重心向它的次级重心连边，形成了一棵点分树。显然点分树的深度不超过logN。这就意味着，给每个点开个数据结构，存储其点分树子树的所有点，每个点的信息只出现了logN次，总空间不超过NlogN。

然后考虑这个问题的动态版本，由于每个点的信息只出现了logN次，我们就暴力更新这logN个信息。根据本题要维护的信息，我们可以用三个大根堆实现。

每个重心维护一个堆C，存储其块内所有点到它父重心的路径长。

每个重心维护一个堆B，表示它每个连通块中到它的最长路径，即是每个子树堆C的堆顶。

在用一个全局堆A统计答案，即所有堆B中的前二大的和。

有一种改进STL优先队列使其可以删除某个元素的方法：

多开一个优先队列存储已经删除的元素，求堆顶时若两个堆堆顶相同就一起把堆顶弹出。

据说还有一种线段树维护括号序列的方法。

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>

using namespace std;
#define mmst(a, b) memset(a, b, sizeof(a))
#define mmcp(a, b) memcpy(a, b, sizeof(b))

typedef long long LL;

const int N=,oo=e9;

void read(int &hy)
{
    hy=;
    char cc=getchar();
    while(cc<'0'||cc>'9')
    cc=getchar();
    while(cc>='0'&&cc<='9')
    {
        hy=(hy<<)+(hy<<)+cc-;
        cc=getchar();
    }
}

struct yy
{
    priority_queue<int> R,D;
    void push(int x) { R.push(x);}
    void pop(int x) { D.push(x);}
    int top()
    {
        while(!D.empty() && R.top()==D.top())
        R.pop(),D.pop();

        return R.top();
    }
    int top2()
    {
        int tmp=top(),ans;
        pop(tmp);
        ans=tmp+top();
        push(tmp);
        if(ans==tmp||tmp==)
        return ;
        return ans;
    }
}A,B[N],C[N];

int to[N],nex[N],head[N],cnt;
int n,m,num,col[N];
bool vis[N];
int dep[N],f[N],pre[N][],p[N],siz[N],g[N],tim[N],times,sum,root;

void add(int u,int v)
{
    to[++cnt]=v;
    nex[cnt]=head[u];
    head[u]=cnt;
}

void dfs(int x,int fa)
{
    if(!dep[x])
    dep[x]=dep[fa]+;

    f[x]=fa;

    if(!pre[x][])
    pre[x][]=fa;

    if(!tim[x])
    tim[x]=++times;

    g[x]=;
    siz[x]=;

    for(int h=head[x];h;h=nex[h])
    if(to[h]!=fa&&!vis[to[h]])
    {
        dfs(to[h],x);
        siz[x]+=siz[to[h]];
        g[x]=max(g[x],siz[to[h]]);
    }
    g[x]=max(g[x],sum-siz[x]);
    if(g[x]<g[root])
    root=x;
}

int dis(int x,int y)
{
    if(x==y)
    return ;

    if(tim[x]>tim[y])
    swap(x,y);
    int hy=y;
    for(int i=;i>=;i--)
    if(tim[pre[y][i]]>tim[x])
    y=pre[y][i];
    return dep[x]+dep[hy]-*dep[pre[y][]];
}

void dfs2(int x)
{
    siz[f[x]]=sum-siz[x];
    vis[x]=;
    for(int h=head[x];h;h=nex[h])
    if(!vis[to[h]])
    {
        sum=siz[to[h]];
        root=;
        dfs(to[h],to[h]);
        p[root]=x;
        dfs2(root);
    }
}

void update(int x)
{
    A.pop(B[x].top2());
    if(!col[x])
    B[x].push();
    else
    B[x].pop();
    A.push(B[x].top2());

    for(int now=x;p[now];now=p[now])
    {
        int len=dis(x,p[now])+;

        A.pop(B[p[now]].top2());
        B[p[now]].pop(C[now].top());
        if(!col[x])
        C[now].push(len);
        else
        C[now].pop(len);

        B[p[now]].push(C[now].top());

        A.push(B[p[now]].top2());

    }
    num-=col[x];
    col[x]=!col[x];
    num+=col[x];
}

int main()
{
    cin>>n;
    for(int i=;i<n;i++)
    {
        int u,v;
        read(u);
        read(v);
        add(u,v);
        add(v,u);
    }

    g[]=oo;
    sum=n;
    dfs(,);

    dfs2(root);

    for(int j=;j<=;j++)
    for(int i=;i<=n;i++)
    pre[i][j]=pre[pre[i][j-]][j-];

    for(int i=;i<=n;i++)
    {
        B[i].push(),B[i].push();
        C[i].push(),C[i].push();
        A.push();
    }

    for(int i=;i<=n;i++)
    update(i);

    cin>>m;
    while(m--)
    {
        char cc=getchar();
        while(cc!='G'&&cc!='C')
        cc=getchar();

        if(cc=='G')
        {
            if(num<=)
            printf("%d\n",num-);
            else
            printf("%d\n",A.top()-);
        }
        else
        {
            int x;
            read(x);
            update(x);
        }
    }
    return ;
}