重剖求调喵/kel

#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

constexpr int N = 2e5 + 5;
int n, m;

int head[N], nxt[N << 1], ver[N << 1], tot;
inline void add (int a, int b) {
    ver[++ tot] = b;
    nxt[tot] = head[a], head[a] = tot;
}

int siz[N], dep[N], hson[N], fath[N];
int dfn[N], bac[N], top[N], idx;
int jmp[N][25];
void decom (int x, int fa) {
	siz[x] = 1, dep[x] = dep[fa] + 1, fath[x] = fa;
	jmp[x][0] = fa;
	for (int i = 1; i <= 20; ++ i) {
		jmp[x][i] = jmp[jmp[x][i - 1]][i - 1];
	}
	int mxsiz = 0;
	for (int i = head[x]; i; i = nxt[i]) {
		int y = ver[i];
		if (y == fa) continue;
		decom(y, x);
		siz[x] += siz[y];
		if (siz[y] > mxsiz) mxsiz = siz[y], hson[x] = y;
	}
}
void dfs (int x, int tp) {
	dfn[x] = ++ idx, bac[idx] = x, top[x] = tp;
	if (hson[x]) dfs(hson[x], tp);
	for (int i = head[x]; i; i = nxt[i]) {
		int y = ver[i];
		if (y == fath[x] or y == hson[x]) continue;
		dfs(y, y);
	}
}
inline int LCA (int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		x = fath[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}
inline int theson (int x, int y) {
	for (int i = 20; i >= 0; -- i) {
		if (dep[jmp[x][i]] > dep[y]) x = jmp[x][i];
	}
	return x;
}
int coltop[N << 1], colbot[N << 1];

struct SegmentTree {
	int col[N << 2], mx[N << 2], tag[N << 2];
	inline void pushup (int p) {
		mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
	}
	inline void pushdown (int p) {
		if (!tag[p]) return;
		tag[p << 1] += tag[p];
		tag[p << 1 | 1] += tag[p];
		mx[p << 1] += tag[p];
		mx[p << 1 | 1] += tag[p];
		tag[p] = 0;
	}
	void build (int p = 1, int l = 1, int r = n) {
		if (l == r) return mx[p] = dep[bac[l]], col[p] = bac[l], void();
		int mid = l + r >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	void update_color (int x, int y, int val, int p = 1, int l = 1, int r = n) {
		if (l >= x and r <= y) return col[p] = max(col[p], val), void();
		int mid = l + r >> 1;
		if (x <= mid) update_color(x, y, val, p << 1, l, mid);
		if (y > mid) update_color(x, y, val, p << 1 | 1, mid + 1, r);
	}
	void update_answer (int x, int y, int val, int p = 1, int l = 1, int r = n) {
		if (l >= x and r <= y) return mx[p] += val, tag[p] += val, void();
		pushdown(p);
		int mid = l + r >> 1;
		if (x <= mid) update_answer(x, y, val, p << 1, l, mid);
		if (y > mid) update_answer(x, y, val, p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	int query_color (int pos, int p = 1, int l = 1, int r = n) {
		if (l == r) return col[p];
		int mid = l + r >> 1;
		if (pos <= mid) return max(col[p], query_color(pos, p << 1, l, mid));
		else return max(col[p], query_color(pos, p << 1 | 1, mid + 1, r));
	}
	int query_answer (int x, int y, int p = 1, int l = 1, int r = n) {
		if (l >= x and r <= y) return mx[p];
		pushdown(p);
		int mid = l + r >> 1, tmp = 0;
		if (x <= mid) tmp = max(tmp, query_answer(x, y, p << 1, l, mid));
		if (y > mid) tmp = max(tmp, query_answer(x, y, p << 1 | 1, mid + 1, r));
		return tmp;
	}
} seg;

inline void update_path (int x, int col) {
	coltop[col] = 1, colbot[col] = x;
	int lst = 0;
	while (x) {
		int ansx = seg.query_answer(dfn[x], dfn[x]);
		int colx = seg.query_color(dfn[x]);
		int tpc = coltop[colx], tpl = top[x];
		int newtop = tpc;
		if (dep[tpl] < dep[tpc]) {
			seg.update_color(dfn[tpc], dfn[x], col);
			seg.update_answer(dfn[tpc], dfn[tpc] + siz[tpc] - 1, 1 - ansx);
			if (lst) seg.update_answer(dfn[lst], dfn[lst] + siz[lst] - 1, ansx - 1);
		} else {
			seg.update_color(dfn[tpl], dfn[x], col);
			seg.update_answer(dfn[tpl], dfn[tpl] + siz[tpl] - 1, 1 - ansx);
			if (lst) seg.update_answer(dfn[lst], dfn[lst] + siz[lst] - 1, ansx - 1);
		}
		if (x != colbot[colx]) {
			int y = theson(colbot[colx], x);
			if (y != lst) {
				seg.update_answer(dfn[y], dfn[y] + siz[y] - 1, 1);
				newtop = y;
			}
		}
		if (dep[tpc] < dep[tpl]) {
			x = jmp[tpl][0], lst = tpl;
		} else {
			x = jmp[tpc][0], lst = tpc;
			if (x != colbot[colx]) coltop[colx] = newtop;
		}
	}
}
inline int query_path (int x, int y) {
	int lca = LCA(x, y);
	return seg.query_answer(dfn[x], dfn[x]) +
		   seg.query_answer(dfn[y], dfn[y]) -
		  (seg.query_answer(dfn[lca], dfn[lca]) << 1)
		   + 1;
}
inline int query_subtree (int x) {
	return seg.query_answer(dfn[x], dfn[x] + siz[x] - 1);
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i < n; ++ i) {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    decom(1, 0);
    dfs(1, 1);
    for (int i = 1; i <= n; ++ i) coltop[i] = colbot[i] = i;
    seg.build();
    int opt, x, y;
    int maxcol = n;
    while (m --) {
    	cin >> opt;
    	switch (opt) {
    		case 1: {
    			cin >> x;
    			update_path(x, ++ maxcol);
				break;
			}
			case 2: {
				cin >> x >> y;
				cout << query_path(x, y) << '\n';
				break;
			}
			case 3: {
				cin >> x;
				cout << query_subtree(x) << '\n';
				break;
			}
		}
	}
    return 0;
}