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。

Sample Input#

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

Sample Output#

4
3
3
4

HINT#

对于100%的数据， N ≤100000, M ≤500000。

动态点分治
将每次点分治中的重心建树
在每个点维护值
本题维护两个堆
C[i] 维护子树中的黑点到起分治父亲的Dis
B[i] 维护子树中C[i]的堆顶

ans 维护答案

#pragma GCC optimize("O3")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='0')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int MAXN = 100005;
struct Priority_queue
{
    __gnu_pbds::priority_queue<int, less<int>, __gnu_pbds::binary_heap_tag> Q1, Q2;
    inline int size()
    {
        return Q1.size() - Q2.size();
    }
    inline void push(const int &x)
    {
        Q1.push(x);
    }
    inline void erase(const int &x)
    {
        Q2.push(x);
    }
    inline int top()
    {
        while (!Q2.empty() && Q1.top() == Q2.top())
        {
            Q1.pop();
            Q2.pop();
        }
        if (!Q1.empty()) return Q1.top();
        else return 0;
    }
    inline int top2()
    {
        if (size() < 2) return 0;
        while (!Q2.empty() && Q1.top() == Q2.top())
        {
            Q1.pop();
            Q2.pop();
        }
        int tmp = Q1.top(); Q1.pop();
        while (!Q2.empty() && Q1.top() == Q2.top())
        {
            Q1.pop();
            Q2.pop();
        }
        int ans = Q1.top(); Q1.push(tmp);
        return ans;
    }
}B[MAXN], C[MAXN], ans;
struct edge
{
    int END, next;
}v[MAXN << 1];
int first[MAXN], p;
inline void add(int a, int b)
{
    v[p].END = b;
    v[p].next = first[a];
    first[a] = p++;
}
int f[MAXN][18];
int dep[MAXN];
inline void PreDFS(int rt, int fa)
{
    dep[rt] = dep[fa] + 1;
    f[rt][0] = fa;
    for (int i = 1; i <= 17; i++) f[rt][i] = f[f[rt][i - 1]][i - 1];
    for (int i = first[rt]; i != -1; i = v[i].next)
    {
        if (v[i].END == fa) continue;
        PreDFS(v[i].END, rt);
    }
}
int sum, Max[MAXN], size[MAXN], root;
bool vis[MAXN];
static inline void GetRoot(int rt, int fa)
{
    size[rt] = 1; Max[rt] = 0;
    for (int i = first[rt]; i != -1; i = v[i].next)
    {
        if (vis[v[i].END] || v[i].END == fa) continue;
        GetRoot(v[i].END, rt);
        size[rt] += size[v[i].END];
        Max[rt] = max(Max[rt], size[v[i].END]);
    }
    Max[rt] = max(Max[rt], sum - size[rt]);
    if (Max[rt] < Max[root]) root = rt;
}
int Fa[MAXN];
static inline void Divide(int rt, int fa)
{
    vis[rt] = 1;
    Fa[rt] = fa;
    // cerr << rt << endl;
    for (int i = first[rt]; i != -1; i = v[i].next)
    {
        if (vis[v[i].END]) continue;
        sum = size[v[i].END], root = 0;
        GetRoot(v[i].END, 0);
        Divide(root, rt);
    }
}
static inline int LCA(int a, int b)
{
    if (dep[a] < dep[b]) swap(a, b);
    int d = dep[a] - dep[b];
    for (int i = 17; i >= 0; i--)
        if (d & (1 << i))
            d -= (1 << i), a = f[a][i];
    if (a == b) return a;
    for (int i = 17; i >= 0; i--)
        if (f[a][i] != f[b][i])
            a = f[a][i], b = f[b][i];
    return f[a][0];
}
static inline int dis(const int &a, const int &b)
{
    return dep[a] + dep[b] - 2 * dep[LCA(a, b)];
}
int Color[MAXN];
static inline void Change_To_Black(const int &Height_root, const int &Child)
{
    if (Height_root == Child)
    {
        B[Height_root].push(0);
        if (B[Height_root].size() == 2)
            ans.push(B[Height_root].top());
    }
    if (!Fa[Height_root]) return;
    int Father = Fa[Height_root];
    int Dis = dis(Father, Child);
    int tmp = C[Height_root].top();
    C[Height_root].push(Dis);
    if (Dis > tmp)
    {
        int size = B[Father].size();
        int tmp2 = B[Father].top() + B[Father].top2();
        if (tmp)
            B[Father].erase(tmp);
        B[Father].push(Dis);
        int now = B[Father].top() + B[Father].top2();
        if (now > tmp2)
        {
            if (size >= 2) ans.erase(tmp2);
            if (B[Father].size() >= 2)
                ans.push(now);
        }
    }
    Change_To_Black(Father, Child);
}
static inline void Change_To_White(const int &Height_root, const int &Child)
{
    if (Height_root == Child)
    {
        if (B[Height_root].size() == 2)
            ans.erase(B[Height_root].top());
        B[Height_root].erase(0);
    }
    if (!Fa[Height_root]) return;
    int Father = Fa[Height_root];
    int Dis = dis(Father, Child);
    int tmp = C[Height_root].top();
    C[Height_root].erase(Dis);
    if (tmp == Dis)
    {
        int size = B[Father].size();
        int tmp2 = B[Father].top() + B[Father].top2();
        B[Father].erase(Dis);
        if (C[Height_root].top())
            B[Father].push(C[Height_root].top());
        int now = B[Father].top() + B[Father].top2();
        if (now < tmp2)
        {
            if (size >= 2)
                ans.erase(tmp2);
            if (B[Father].size() >= 2)
                ans.push(now);
        }
    }
    Change_To_White(Father, Child);
}
int main()
{
    memset (first, -1, sizeof (first));
    int n = read();
    for (int i = 1; i < n; i++)
    {
        int a = read(), b = read();
        add(a, b);
        add(b, a);
        // cerr << i << endl;
    }
    PreDFS(1, 0);
    
    Max[0] = sum = n;
    GetRoot(1, 0);
    
    Divide(root, 0);
    // cerr << "11!!" << endl;
    for (int i = 1; i <= n; i++)
    {
        Color[i] = 1;
        // cerr << i << endl;
        C[i].push(0);
        // Change_To_Black(i, i);
    }
    for (int i = 1; i <= n; i++)
    {
        Change_To_Black(i, i);
        // cerr << i << endl;        
    }
    // for (int i = 1; i <= n; i++) cerr << "i fa is " << Fa[i] << endl;
    int m = read();
    char s[10];
    for (int i = 1; i <= m; i++)
    {
        // cerr << i << endl;
        scanf ("%s", s);
        if (s[0] == 'C')
        {
            int k = read();
            if (Color[k])
            {
                Color[k] = 0;
                Change_To_White(k, k);
            }
            else
            {
                Color[k] = 1;
                Change_To_Black(k, k);
            }
        }
        else
            printf ("%d\n", ans.top());
    }
}