Problem

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，输出一个非负整数，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出 0；若所有房间的灯都开着，输出 -1。

Sample Input

Sample Output

HINT

对于20%的数据， $N \leq 50$, $Q\leq 100$；

对于60%的数据， $N \leq 3000$, $Q \leq 10000$

对于100%的数据， $N \leq 100000$, $Q \leq 500000$

Solution

Analysis

这里给出动态点分治的一个做法（括号序列做法也许以后会补？)

简单而言就是堆去维护每个点它能到达最深的点，两条边相加。

这样子做会出现不合法的，那就再维护堆对于该点的每个儿子。

Attention

简单证明一下淀粉树的正确性（防止我自己迷惑，应该大家都会这个证明（我太菜了））：

每个点把树分成了$\sum children$个部分，这些部分都互相连边，且其余的边一定不经过$root$，那么分治下去就是子问题。

（所以淀粉树上两点的距离即使不是1也是可以正确的）（这好像就是点分治的正确性emmm）

Code

自带大常数，好乱啊（也许会重构？

//Code by Enderturtle
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repe(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define il inline
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;
il void filejudge(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
il int read(){
    int x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
/*----- head end -----*/
const int N=100010;
int n,cnt;
struct node{
    priority_queue<int> q1,q2;
    il void push(int x){ q1.push(x);}
    il void erase(int x){ q2.push(x);}
    il int size(){ return q1.size()-q2.size();}
    il int top(){
        while(!q2.empty() && q1.top()==q2.top()) q1.pop(),q2.pop();
        return q1.top();
    }
    il void pop(){
        while(!q2.empty() && q1.top()==q2.top()) q1.pop(),q2.pop();
        q1.pop();
    }
    il int top2(){
        int tmp=top();pop();
        int res=top();push(tmp);
        return res;
    }
} h1[N],h2[N],ans;
struct Edge{ int v,nxt;} e[N<<1];int tot,head[N];
il void add_edge(int u,int v){ e[++tot]=(Edge){v,head[u]};head[u]=tot;}
il void link(int u,int v){ add_edge(u,v),add_edge(v,u);}
namespace slpf{
    int sz[N],fa[N],top[N],son[N],dep[N];
    il void dfs1(int u,int f){
        sz[u]=1;dep[u]=dep[f]+1;fa[u]=f;
        repe(i,u){
            int v=e[i].v;
            if(v==f) continue;
            dfs1(v,u);
            sz[u]+=sz[v];
            if(sz[v]>sz[son[u]]) son[u]=v;
        }
    }
    il void dfs2(int u,int topf){
        top[u]=topf;
        if(!son[u]) return;
        dfs2(son[u],topf);
        repe(i,u){
            int v=e[i].v;
            if(v==fa[u] || v==son[u]) continue;
            dfs2(v,v);
        }
    }
    il void init(){ dfs1(1,1);dfs2(1,1);}
    il int lca(int u,int v){
        while(top[u]!=top[v]){
            if(dep[top[u]]<dep[top[v]]) swap(u,v);
            u=fa[top[u]];
        }
        if(dep[u]>dep[v]) swap(u,v);
        return u;
    }
    il int getdis(int u,int v){
        int c=lca(u,v);
        return dep[u]+dep[v]-2*dep[c];
    }
}
using slpf::getdis;
int sz[N],fa[N],mx[N],treesz,root;bool vis[N],st[N];
il void getsz(int u,int f){
    sz[u]=1;
    repe(i,u){
        int v=e[i].v;
        if(v==f || vis[v]) continue;
        getsz(v,u);
        sz[u]+=sz[v];
    }
}
il void getroot(int u,int f){
    mx[u]=0;
    repe(i,u){
        int v=e[i].v;
        if(v==f || vis[v]) continue;
        getroot(v,u);
        mx[u]=max(mx[u],sz[v]);
    }
    mx[u]=max(mx[u],treesz-mx[u]);
    if(mx[u]<mx[root]) root=u;
}
il void nxtroot(int u,int f){
    getsz(u,f);
    root=0;treesz=sz[u];
    getroot(u,f);
}
il void calc(int id,int u,int f){
    if(!st[u]) h2[root].push(getdis(u,id));
    repe(i,u){
        int v=e[i].v;
        if(v==f || vis[v]) continue;
        calc(id,v,u);
    }
}
il void solve(int u){
    vis[u]=1;
    if(!st[u]) h1[u].push(0);
    repe(i,u){
        int v=e[i].v;
        if(vis[v]) continue;
        nxtroot(v,u);
        fa[root]=u;
        calc(u,root,root);
        if(h2[root].size()) h1[u].push(h2[root].top());
        solve(root);
    }
    if(h1[u].size()>1) ans.push(h1[u].top()+h1[u].top2());
}
il void turn_on(int u){
    st[u]=1;cnt--;
    if(h1[u].size()>1) ans.erase(h1[u].top()+h1[u].top2());
    h1[u].erase(0);
    if(h1[u].size()>1) ans.push(h1[u].top()+h1[u].top2());
    int now=u;
    for(;fa[u]!=0;u=fa[u]){
        int f=fa[u];
        if(h1[f].size()>1) ans.erase(h1[f].top()+h1[f].top2());
        int dis=getdis(now,f);
        h1[f].erase(h2[u].top());
        h2[u].erase(dis);
        if(h2[u].size()) h1[f].push(h2[u].top());
        if(h1[f].size()>1) ans.push(h1[f].top()+h1[f].top2());
    }
}
il void turn_off(int u){
    st[u]=0;cnt++;
    if(h1[u].size()>1) ans.erase(h1[u].top()+h1[u].top2());
    h1[u].push(0);
    if(h1[u].size()>1) ans.push(h1[u].top()+h1[u].top2());
    int now=u;
    for(;fa[u]!=0;u=fa[u]){
        int f=fa[u];
        if(h1[f].size()>1) ans.erase(h1[f].top()+h1[f].top2());
        int dis=getdis(now,f);
        if(h2[u].size()) h1[f].erase(h2[u].top());
        h2[u].push(dis);
        h1[f].push(h2[u].top());
        if(h1[f].size()>1) ans.push(h1[f].top()+h1[f].top2());
    }
}
char opt[3];
int main(){
    n=read();
    rep(i,2,n){ int u=read(),v=read();link(u,v);}
    slpf::init();
    mx[0]=n+1;cnt=n;
    nxtroot(1,1);
    solve(root);
    int Q=read();
    while(Q--){
        scanf("%s",opt);
        if(opt[0]=='G'){
            if(cnt<=1) printf("%d\n",cnt-1);
            else printf("%d\n",ans.top());
        }else{
            int x=read();
            if(st[x]) turn_off(x);
            else turn_on(x);
        }
    }
    return 0;
}

[ZJOI2007]捉迷藏