记录编号	218551	评测结果	AAAAAAAAAT
题目名称	[ZJOI 2007]捉迷藏	最终得分	90
用户昵称	lyxin65	是否通过	未通过
代码语言	C++	运行时间	9.757 s
提交时间	2016-01-09 23:57:08	内存使用	24.44 MiB

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

#define cls(x, y) memset(x, y, sizeof(x))
#define fly(...) fprintf(stderr, __VA_ARGS__)

inline int read()
{
	int x = 0, f = 1, c;
	while(c = getchar(), c < '0' || c > '9') if(c == '-') f = -1;
	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
	return x * f;
}

inline char mygetchar()
{
	static char ch;
	while(ch = getchar(), ch < 'A' || ch > 'Z');
	return ch;
}

const int maxn = 100005;
const int maxm = 200005;
const int maxlog = 19;

int n, m, G, S, cnt, dfs_clock;
int head[maxn], size[maxn];
int next[maxm], v[maxm];
int fa[maxn], f[maxn];
int depth[maxn], pos[maxn];
int rmq[maxlog][maxm], LOG[maxm];
bool done[maxn]; int light[maxn];

struct Heap
{
	multiset<int> data;

	int size() { return data.size(); }
	int top() { return *data.rbegin(); }
	int get() { return top() + *++data.rbegin(); }
	void ins(int x) { data.insert(x); }
	void del(int x) { data.erase(data.find(x)); }

} A[maxn], B[maxn], C;
// A - 记录子树中所有节点到父亲节点的距离
// B - 记录所有子节点的堆顶
// C - 记录所有B中最大值和次大值之和

void addedge(int a, int b)
{
	v[m] = b, next[m] = head[a], head[a] = m++;
	v[m] = a, next[m] = head[b], head[b] = m++;
}

void input()
{
	n = read(); cls(head, -1);
	for(int i = 1; i < n; ++i)
		addedge(read(), read());
}

void root(int x, int p)
{
	size[x] = 1; f[x] = 0;
	for(int i = head[x]; ~i; i = next[i]) if(v[i] != p && !done[v[i]])
		{ root(v[i], x); size[x] += size[v[i]]; f[x] = max(f[x], size[v[i]]); }
	f[x] = max(f[x], S - size[x]); if(G == -1 || f[x] < f[G]) G = x;
}

void divide(int x, int p)
{
	fa[x] = p; done[x] = 1;
	for(int i = head[x]; ~i; i = next[i]) if(!done[v[i]])
		{ G = -1; S = size[v[i]]; root(v[i], x); divide(G, x); }
}

void dfs(int x, int p)
{
	rmq[0][pos[x] = ++dfs_clock] = depth[x] = depth[p] + 1;
	for(int i = head[x]; ~i; i = next[i]) if(v[i] != p)
		{ dfs(v[i], x); rmq[0][++dfs_clock] = depth[x]; }
}

void init_rmq()
{
	for(int i = 2; i <= dfs_clock; ++i) LOG[i] = LOG[i>>1] + 1;
	for(int i = 0; i < LOG[dfs_clock]; ++i)
		for(int j = 1; j+(1<<i+1)-1 <= dfs_clock; ++j)
			rmq[i+1][j] = min(rmq[i][j], rmq[i][j+(1<<i)]);
}

inline int lca(int x, int y)
{
	x = pos[x]; y = pos[y]; if(x > y) swap(x, y);
	int L = LOG[y-x+1]; return min(rmq[L][x], rmq[L][y-(1<<L)+1]);
}

inline int dist(int x, int y) { return depth[x] + depth[y] - 2 * lca(x, y); }

#define remove(x) if(x.size() >= 2) C.del(x.get())
#define insert(x) if(x.size() >= 2) C.ins(x.get())
#define work(x, v) flag == 1 ? x.del(v) : x.ins(v)

void modify(int x, int flag)
{
	remove(B[x]); work(B[x], 0); insert(B[x]);
	for(int i = x; i; i = fa[i])
	{
		remove(B[fa[i]]);
		if(A[i].size()) B[fa[i]].del(A[i].top());
		work(A[i], dist(x, fa[i]));
		if(A[i].size()) B[fa[i]].ins(A[i].top());
		insert(B[fa[i]]);
	}
}

void build()
{
	G = -1; S = n; root(1, 0); divide(G, 0);
	dfs(1, 0); init_rmq(); cls(light, -1), cnt = n;
	for(int i = 1; i <= n; ++i) modify(i, -1);
}

inline void change(int x) { cnt += light[x]; modify(x, light[x] = -light[x]); }

void solve()
{
	register int Q = read();
	while(Q--)
	{
		if(mygetchar() == 'G')
		{
			if(!cnt) puts("-1");
			else if(cnt == 1) puts("0");
			else printf("%d\n", C.top());
		}
		else change(read());
	}
}

int main()
{
	freopen("hide.in", "r", stdin);
	freopen("hide.out", "w", stdout);
	
	input();
	build();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}