爆零力。

分析

T1

给定 $S=n^n,n\in\mathbb{N^{*}}$ 求 $n$ 。

用的 NTT，OJ 的评测机太慢了，常数爆炸。

正解是当 $n>2$ 时，每一个 $n^n$ 位数都不同，且等于 $\left\lfloor n\log_{10}n\right\rfloor + 1$ ，然后二分。

T2

动态，在给定点集中，找树的直径。

其中用到 $\mathcal{O}(1)$ LCA，方法是用欧拉序（DFS 序，但重复访问的点重复加入序里）转为序列，然后 ST 表求两点间深度最小的点。

贴个没过的代码：

const int N = 1e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n, q;
int head[N], tot;
struct edge {
	int to, nxt;
}e[N << 1];
void Add(int u, int v) {
	e[++tot] = (edge) {v, head[u]}, head[u] = tot;
}
int dep[N], dfn, eln;
int a[N << 1], b[N], f[N][25];
int dpos[N], epos[N];
void dfs(int u, int fa) {
	dep[u] = dep[fa] + 1;
	f[u][0] = u;
	a[++eln] = u;
	b[++dfn] = u;
	dpos[u] = dfn;
	epos[u] = eln;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (v == fa) continue;
		dfs(v, u);
		a[++eln] = u;
	}
}

int LCA(int u, int v) {
	u = epos[u], v = epos[v];
	if (u > v) u ^= v ^= u ^= v;
	int len = log2(v - u + 1);
	if (dep[f[u][len]] < dep[f[v - (1 << len) + 1][len]]) return f[u][len];
	return f[v - (1 << len) + 1][len];
}
int distance (int u, int v) { return 2 * dep[LCA(u, v)] - dep[u] - dep[v]; }

int type[N];
struct SegmentTree {
	struct Tree {
		int l, r, p[2];
	}t[N << 2];

	void PushUp (int p) {
		int p1, p2, dis = 0, flag = 0;
		if (!type[t[p << 1].p[0]] && !type[t[p << 1].p[1]] && dis < distance(t[p << 1].p[0], t[p << 1].p[1])) dis = distance(t[p << 1].p[0], t[p << 1].p[1]), p1 = t[p << 1].p[0], p2 = t[p << 1].p[1], flag = 1;
		if (!type[t[p << 1 | 1].p[0]] && !type[t[p << 1].p[1]] && dis < distance(t[p << 1 | 1].p[0], t[p << 1].p[1])) dis = distance(t[p << 1 | 1].p[0], t[p << 1].p[1]), p1 = t[p << 1 | 1].p[0], p2 = t[p << 1].p[1], flag = 1;
		if (!type[t[p << 1 | 1].p[0]] && !type[t[p << 1].p[0]] && dis < distance(t[p << 1 | 1].p[0], t[p << 1].p[0])) dis = distance(t[p << 1 | 1].p[0], t[p << 1].p[0]), p1 = t[p << 1 | 1].p[0], p2 = t[p << 1].p[0], flag = 1;
		if (!type[t[p << 1].p[0]] && !type[t[p << 1 | 1].p[1]] && dis < distance(t[p << 1].p[0], t[p << 1 | 1].p[1])) dis = distance(t[p << 1].p[0], t[p << 1 | 1].p[1]), p1 = t[p << 1].p[0], p2 = t[p << 1 | 1].p[1], flag = 1;
		if (!type[t[p << 1].p[1]] && !type[t[p << 1 | 1].p[1]] && dis < distance(t[p << 1].p[1], t[p << 1 | 1].p[1])) dis = distance(t[p << 1].p[1], t[p << 1 | 1].p[1]), p1 = t[p << 1].p[1], p2 = t[p << 1 | 1].p[1], flag = 1;
		if (!type[t[p << 1 | 1].p[0]] && !type[t[p << 1 | 1].p[1]] && dis < distance(t[p << 1 | 1].p[0], t[p << 1 | 1].p[1])) 
			dis = distance(t[p << 1 | 1].p[0], t[p << 1 | 1].p[1]), p1 = t[p << 1 | 1].p[0], p2 = t[p << 1 | 1].p[1], flag = 1;
		if (!flag) {
			if (!type[t[p << 1].p[0]]) p1 = p2 = t[p << 1].p[0], flag = 1;
			if (!type[t[p << 1].p[1]]) p1 = p2 = t[p << 1].p[1], flag = 1;
			if (!type[t[p << 1 | 1].p[0]]) p1 = p2 = t[p << 1 | 1].p[0], flag = 1;
			if (!type[t[p << 1 | 1].p[1]]) p1 = p2 = t[p << 1 | 1].p[1], flag = 1;
		} 
		if (!flag) p1 = p2 = t[p << 1].p[0];
		t[p].p[0] = p1, t[p].p[1] = p2;
	}
	void Build(int p, int l, int r) {
		t[p].l = l, t[p].r = r;
		if (t[p].l == t[p].r) {
			t[p].p[0] = t[p].p[1] = b[t[p].l];
			return;
		}
		int mid = t[p].l + t[p].r >> 1;
		Build (p << 1, l, mid);
		Build (p << 1 | 1, mid + 1, r);
		PushUp(p);
	}
	void Modify(int p, int x) {
		if (t[p].l == t[p].r) {
			type[x] ^= 1;
			return;
		}
		int mid = t[p].l + t[p].r >> 1;
		if (x <= mid) Modify (p << 1, x);
		else Modify (p << 1 | 1, x);
		PushUp(p);
	}
}t;

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = Read(), q = Read();
	for (int i = 1; i < n; i++) {
		int u = Read(), v = Read();
		Add(u, v), Add(v, u);
	}
	dfs(1, 0);
	for (int j = 1; j <= 22; j++)
		for (int i = 1; i + (1 << j) <= eln; i++)
			if (dep[f[i][j-1]] < dep[f[i + (1 << j - 1)][j-1]]) f[i][j] = f[i][j-1];
			else f[i][j] = f[i + (1 << j-1)][j-1];
	t.Build(1, 1, n);
//	return 0;
	for (; q--; ) {
		string s;
		cin >> s;
		if (s[0] == 'G') {
			printf ("%d\n", distance(t.t[1].p[0], t.t[1].p[1]));
		} else {
			int x = Read();
			t.Modify(1, b[x]);
		}
	}
	return 0;
}