有趣题，代码超好写，而且思路超有趣！！！
首先发现操作 1 的操作都是某个点到根，不难发现这样每种颜色一定对应着树上的一条链。那么操作 2 可以直接树上查分求答案，这样我们只需要考虑维护每个点到根的链的数量了。
怎么维护链的数量？发现这个操作 1 长得和 LCT 的 Access 操作一模一样啊，所以我们直接上 LCT 维护这个东西就行了。
考虑具体怎么维护，一个点到根的链的数量等同于这个点到根经过的虚边的数量，这样我们只需要在 Access 更改虚实边的时候，对应的在线段树上区间修改一下即可。
注意到我们需要找到这条链的链顶，直接不断跳左儿子就能找到链顶。但是这个复杂度是错的，可以考虑每次跳完之后 Splay 上来保证复杂度，或者直接维护一个标记表示这个点一直跳左儿子跳到的节点即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n;
vector<int> e[MAXN];
int dep[MAXN];
int dfn[MAXN], ed[MAXN], dcnt;
struct SegmentTree {
struct Node {
int val, tag;
} t[MAXN << 2];
#define lc (i << 1)
#define rc (i << 1 | 1)
void tag(int i, int v) { t[i].val += v, t[i].tag += v; }
void pushDown(int i) { tag(lc, t[i].tag), tag(rc, t[i].tag), t[i].tag = 0; }
void add(int a, int b, int v, int i = 1, int l = 1, int r = n) {
if (a <= l && r <= b) return tag(i, v);
int mid = (l + r) >> 1;
pushDown(i);
if (a <= mid) add(a, b, v, lc, l, mid);
if (b > mid) add(a, b, v, rc, mid + 1, r);
t[i].val = max(t[lc].val, t[rc].val);
}
int query(int a, int b, int i = 1, int l = 1, int r = n) {
if (a <= l && r <= b) return t[i].val;
int mid = (l + r) >> 1;
pushDown(i);
if (b <= mid) return query(a, b, lc, l, mid);
if (a > mid) return query(a, b, rc, mid + 1, r);
return max(query(a, b, lc, l, mid), query(a, b, rc, mid + 1, r));
}
#undef lc
#undef rc
} st;
int fa[MAXN][22];
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 18; i >= 0; i--) if (dep[fa[x][i]] >= dep[y])
x = fa[x][i];
if (x == y) return x;
for (int i = 18; i >= 0; i--) if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
void dfs(int u, int pre) {
dep[u] = dep[pre] + 1, dfn[u] = ++dcnt;
fa[u][0] = pre;
for (int i = 1; i <= 18; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
st.add(dfn[u], dfn[u], dep[u]);
for (int v : e[u]) if (v != pre) {
dfs(v, u);
}
ed[u] = dcnt;
}
struct LinkCutTree {
int t[MAXN][2], fa[MAXN], rev[MAXN], rt[MAXN];
#define lc(x) t[x][0]
#define rc(x) t[x][1]
#define ident(x) (t[fa[x]][1] == x)
#define nroot(x) (t[fa[x]][0] == x || t[fa[x]][1] == x)
void tag(int x) { rev[x] ^= 1, swap(lc(x), rc(x)); }
void pushDown(int x) { if (rev[x]) tag(lc(x)), tag(rc(x)), rev[x] = 0; }
void pushUp(int x) { rt[x] = lc(x) ? rt[lc(x)] : x; }
void rotate(int x) {
int f = fa[x], ff = fa[f];
int a = ident(x), b = ident(f);
if (nroot(f)) t[ff][b] = x;
fa[x] = ff;
t[f][a] = t[x][!a];
fa[t[x][!a]] = f;
t[x][!a] = f;
fa[f] = x;
pushUp(f), pushUp(x);
}
void splay(int x) {
stack<int> st; st.push(x);
int y = x; while (nroot(y)) y = fa[y], st.push(y);
while (!st.empty()) pushDown(st.top()), st.pop();
while (nroot(x)) {
if (nroot(fa[x])) rotate(ident(x) == ident(fa[x]) ? fa[x] : x);
rotate(x);
}
pushUp(x);
}
void access(int x) {
for (int y = 0; x; x = fa[y = x]) {
splay(x);
if (rc(x)) st.add(dfn[rt[rc(x)]], ed[rt[rc(x)]], 1);
if (y) st.add(dfn[rt[y]], ed[rt[y]], -1);
rc(x) = y, pushUp(x);
}
}
} lct;
int m;
int query(int x) {
return st.query(dfn[x], dfn[x]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v), e[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
lct.fa[i] = fa[i][0];
lct.rt[i] = i;
}
while (m--) {
int op, x; scanf("%d%d", &op, &x);
if (op == 1) {
lct.access(x);
} else if (op == 2) {
int y; scanf("%d", &y);
printf("%d\n", query(x) + query(y) - 2 * query(lca(x, y)) + 1);
} else if (op == 3) {
printf("%d\n", st.query(dfn[x], ed[x]));
}
}
return 0;
}