RT

做法是树链剖分+线段树，最后一个点一直 T

代码：

#include <cstdio>
#include <vector>
const int MAXN = 2e5 + 5;
using namespace std;
int n, m, idx, T, u, v;
int sz[MAXN], p[MAXN], dep[MAXN], dfn[MAXN], tp[MAXN];
int segtree[MAXN << 4], segtree_lc[MAXN << 4], segtree_rc[MAXN << 4], laz_col[MAXN << 4];
vector<int> adj[MAXN];
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
inline void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
	return;
}
inline int dfs_sz(int cur = 1, int par = 1) {
	sz[cur] = 1;
	p[cur] = par;
	dep[cur] = dep[par] + 1;
	for (int chi : adj[cur]) {
		if (chi == par) continue;
		sz[cur] += dfs_sz(chi, cur);
	}
	return sz[cur];
}
inline void dfs_hld(int cur = 1, int par = 1, int top = 1) {
	dfn[cur] = ++idx;
	tp[cur] = top;
	int h_chi = -1, h_sz = -1;
	for (int chi : adj[cur]) {
		if (chi == par) continue;
		if (sz[chi] > h_sz) {
			h_sz = sz[chi];
			h_chi = chi;
		}
	}
	if (h_sz == -1) return;
	dfs_hld(h_chi, cur, top);
	for (int chi : adj[cur]) {
		if (chi == par || chi == h_chi) continue;
		dfs_hld(chi, cur, chi);
	}
}
inline void push_up(int node) {
	segtree[node] = segtree[node << 1] + segtree[node << 1 | 1] + (segtree_rc[node << 1] == segtree_lc[node << 1 | 1]);
	segtree_lc[node] = segtree_lc[node << 1];
	segtree_rc[node] = segtree_rc[node << 1 | 1];
}
inline void push_down(int node, int len) {
	if (!laz_col[node]) return;
	laz_col[node << 1] = laz_col[node << 1 | 1] = laz_col[node];
	segtree_lc[node << 1] = segtree_rc[node << 1] = segtree_lc[node << 1 | 1] = segtree_rc[node << 1 | 1] = laz_col[node];
	segtree[node << 1] = (len - len / 2) - 1;
	segtree[node << 1 | 1] = (len / 2) - 1;
	laz_col[node] = 0;
}
inline void build(int l = 1, int r = n, int node = 1) {
	if (l == r) return void(segtree_lc[node] = segtree_rc[node] = laz_col[node] = -l);
	int mid = (l + r) >> 1;
	build(l, mid, node << 1);
	build(mid + 1, r, node << 1 | 1);
	push_up(node);
}
inline void update(int l, int r, int c, int cl = 1, int cr = n, int node = 1) {
	if (l <= cl && cr <= r) {
		segtree[node] = cr - cl;
		segtree_lc[node] = segtree_rc[node] = laz_col[node] = c;
		return;
	}
	push_down(node, cr - cl + 1);
	int mid = (cl + cr) >> 1;
	if (mid >= l) update(l, r, c, cl, mid, node << 1);
	if (mid < r) update(l, r, c, mid + 1, cr, node << 1 | 1);
	push_up(node);
}
inline void update_path(int x, int y, int c) {
	while (tp[x] != tp[y]) {
		if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
		update(dfn[tp[x]], dfn[x], c);
		x = p[tp[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	update(dfn[x], dfn[y], c);
}
inline int query_node(int p, int l = 1, int r = n, int node = 1) {
	if (l == r) return laz_col[node];
	push_down(node, r - l + 1);
	int mid = (l + r) >> 1;
	if (p <= mid) return query_node(p, l, mid, node << 1);
	else return query_node(p, mid + 1, r, node << 1 | 1);
}
inline int query(int l, int r, int cl = 1, int cr = n, int node = 1) {
	if (l <= cl && cr <= r) return segtree[node];
	push_down(node, cr - cl + 1);
	int mid = (cl + cr) >> 1;
	if (mid >= r) {
		return query(l, r, cl, mid, node << 1);
	} else if (mid < l) {
		return query(l, r, mid + 1, cr, node << 1 | 1);
	} else {
		int tmp_res = 0;
		tmp_res += query(l, r, cl, mid, node << 1);
		tmp_res += query(l, r, mid + 1, cr, node << 1 | 1);
		if (query_node(mid) == query_node(mid + 1)) tmp_res++;
		return tmp_res;
	}
}
inline int query_path(int x, int y) {
	int tmp_res = 0;
	while (tp[x] != tp[y]) {
		if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
		tmp_res += query(dfn[tp[x]], dfn[x]) + (query_node(dfn[p[tp[x]]]) == query_node(dfn[tp[x]]));
		x = p[tp[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	tmp_res += query(dfn[x], dfn[y]);
	return tmp_res;
}
inline void init() {
	idx = 0;
	for (int i = 1; i <= n; ++i) {
		adj[i].clear();
		sz[i] = p[i] = dep[i] = dfn[i] = tp[i] = 0;
	}
	for (int i = 1; i <= n << 4; ++i) {
		segtree[i] = segtree_lc[i] = segtree_rc[i] = laz_col[i] = 0;
	}
}
inline void solve() {
	n = read(), m = read();
	init();
	for (int i = 1; i < n; ++i) {
		u = read(), v = read();
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs_sz();
	dfs_hld();
	build();
	while (m--) {
		int opr, a, b;
		opr = read(), a = read(), b = read();
		if (opr == 1) {
			update_path(a, b, m);
		} else {
			write(query_path(a, b));
			putchar('\n');
		}
	}
}
int main() {
	T = read();
	while (T--) {
		solve();
	}
}