这道题用来理解LCT还是蛮不错的，如果是笨重的LCT完全体就会在洛谷上卡常T掉第4组，但是这道题明显可以省略掉很多多余操作。
我们先看看如果按照正常的LCT,会有这样一些操作：
inline void makeroot(register int x) {
access(x); splay(x); pushr(x);
}
inline void split(register int x, register int y) {
makeroot(x); access(y); splay(y);
}
inline void Link(register int x, register int y) {
makeroot(x); fa[x] = y;
}
makeroot为换根，Link为连边，split为连出棵splay:x-y并将y变为根。
在正常的LCT题目中换根是必不可少的，但在本题中却可以省掉。
因为题目中保证以1为根，且查询为1到x的距离，这样就保证了根节点可以不变。
所以换根操作就可以果断放弃掉，大大的优化了常数。
所以就可以过啦！
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const unsigned int maxn = 250010;
5 int ch[maxn][2], val[maxn], sum[maxn], fa[maxn];
6 inline bool isroot(int x) {
7 return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
8 }
9 inline void pushup(int x) {
10 sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x];
11 }
12 inline void rotate(int x) {
13 int y = fa[x], z = fa[y];
14 int k = ch[y][1] == x;
15 if (!isroot(y))
16 ch[z][ch[z][1] == y] = x;
17 fa[x] = z; ch[y][k] = ch[x][k ^ 1]; fa[ch[x][k ^ 1]] = y;
18 ch[x][k ^ 1] = y; fa[y] = x;
19 pushup(y); pushup(x);
20 }
21 inline void splay(int x) {
22 while (!isroot(x)) {
23 int y = fa[x];
24 int z = fa[y];
25 if (!isroot(y))
26 rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y);
27 rotate(x);
28 }
29 pushup(x);
30 }
31 inline void access(int x) {
32 for (int y = 0; x; x = fa[y = x])
33 splay(x), ch[x][1] = y, pushup(x);
34 }
35 char s[2];
36 int main() {
37 int n, m, x, y;
38 scanf("%d", &n);
39 for (int i = 2; i <= n; ++i)
40 val[i] = 1;
41 for (int i = 1; i < n; ++i) {
42 scanf("%d%d", &x, &y);
43 if (x > y)
44 swap(x, y);
45 fa[y] = x;
46 }
47 scanf("%d", &m);
48 m += n - 1;
49 while (m--) {
50 scanf("%s", s);
51 if (s[0] == 'A') {
52 scanf("%d%d", &x, &y);
53 if (x > y)swap(x, y);
54 splay(y);
55 val[y] = 0, pushup(y);
56 }
57 else {
58 scanf("%d", &x);
59 access(x); splay(x);
60 printf("%d\n", sum[x]);
61 }
62 }
63 }