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());
}
}