[数据结构与算法]【数据结构】轻重链剖分（总结）

?
很早就知道这个东西了，也只是知道（NOI 大纲上这玩意不属于提高级）。

然后题目4632逼着我去学树链剖分。

去 OI wiki 上看了一会，花了点时间对着把模板打了。

这个东西可以看作是 dfs 序的进阶玩法。

将树划分成若干条连续的链，它们在 dfs 序上对应的区间也是连续的。

于是上数据结构维护。

我们给出一些定义：

定义 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。

定义 轻子节点 表示剩余的所有子结点。

从这个结点到重子节点的边为 重边。

到其他轻子节点的边为 轻边。

若干条首尾衔接的重边构成 重链。

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

可以发现，树上每个节点都属于且仅属于一条重链。

重链开头的结点不一定是重子节点（因为重边是对于每一个结点都有定义的）。

所有的重链将整棵树 完全剖分。

在剖分时 重边优先遍历，最后树的 DFN 序上，重链内的 DFN 序是连续的。按 DFN 排序后的序列即为剖分后的链。

一颗子树内的 DFN 序是连续的。

可以发现，当我们向下经过一条 轻边 时，所在子树的大小至少会除以二。

因此，对于树上的任意一条路径，把它拆分成从 lca 处分别向两边往下走，分别最多走 log 次，因此，树上的每条路径都可以被拆分成不超过 log 条重链。

对于树上路径（$u\to v$）的修改，我们参考倍增求 lca 的方法，每次选取 u,v 中深度较大的那个往上跳，遇到重链直接跳到重链顶部，轻边就暴力跳 father。

由此，我们得到了一个可以在 $O(lo{g}^{2}n)$ 的时间内对树的任意两点之间的路径和任意一点的子树进行修改、查询的数据结构。

树剖常数较小，大多数情况跑不满，可以放心食用。

模板题：

Luogu P3384
可以让你熟悉树链剖分的使用和各基本操作。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define N 100005
int n, m, r, p;
int num[N];
int first[N << 1], Next[N << 1], to[N << 1], tot;
inline void add(int x, int y)
{
	Next[++tot] = first[x];
	first[x] = tot;
	to[tot] = y;
	return;
}
int fa[N], dep[N], size[N], hson[N];
void dfs1(int u)
{
	size[u] = 1;
	for(int i = first[u]; i; i = Next[i])
	{
		int v = to[i];
		if(dep[v])
		{
			continue;
		}
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs1(v);
		size[u] += size[v];
		if(!hson[u] || (size[v] > size[hson[u]]))
		{
			hson[u] = v;
		}
	}
	return;
}
int top[N], dfn[N], rnk[N], sign;
void dfs2(int u, int fr)
{
	top[u] = fr;
	dfn[u] = ++sign;
	rnk[sign] = u;
	if(!hson[u])
	{
		return;
	}
	dfs2(hson[u], fr);
	for(int i = first[u]; i; i = Next[i])
	{
		int v = to[i];
		if(v == fa[u] || v == hson[u])
		{
			continue;
		}
		dfs2(v, v);
	}
	return;
}
class segment_tree
{
	private:
	struct node
	{
		int l, r, sum, tag;
	};
	node tree[N << 2];
	inline void pushup(int root)
	{
		tree[root].sum = (tree[root << 1].sum + tree[root << 1 | 1].sum) % p;
		return;
	}
	inline void addtag(int root, int v)
	{
		tree[root].tag += v;
		tree[root].tag %= p;
		tree[root].sum += ((tree[root].r - tree[root].l + 1) * v) % p;
		tree[root].sum %= p;
		return;
	}
	inline void pushdown(int root)
	{
		if(tree[root].tag)
		{
			addtag(root << 1, tree[root].tag);
			addtag(root << 1 | 1, tree[root].tag);
			tree[root].tag = 0;
		}
		return;
	}
	public:
	void build(int root, int l, int r)
	{
		tree[root].l = l;
		tree[root].r = r;
		if(l == r)
		{
			tree[root].sum = num[rnk[l]] % p;
			return;
		}
		int mid = (l + r) >> 1;
		build(root << 1, l, mid);
		build(root << 1 | 1, mid + 1, r);
		pushup(root);
		return;
	}
	void update(int root, int L, int R, int v)
	{
		if(L <= tree[root].l && tree[root].r <= R)
		{
			addtag(root, v);
			return;
		}
		pushdown(root);
		int mid = (tree[root].l + tree[root].r) >> 1;
		if(L <= mid)
		{
			update(root << 1, L, R, v);
		}
		if(mid < R)
		{
			update(root << 1 | 1, L, R, v);
		}
		pushup(root);
		return;
	}
	int querysum(int root, int L, int R)
	{
		if(L <= tree[root].l && tree[root].r <= R)
		{
			return tree[root].sum;
		}
		pushdown(root);
		int mid = (tree[root].l + tree[root].r) >> 1, ret = 0;
		if(L <= mid)
		{
			ret += querysum(root << 1, L, R);
			ret %= p;
		}
		if(mid < R)
		{
			ret += querysum(root << 1 | 1, L, R);
			ret %= p;
		}
		pushup(root);
		return ret;
	}
};
segment_tree T;
inline void addline(int x, int y, int v)
{
	v %= p;
	int fx = top[x], fy = top[y];
	while(fx != fy)
	{
		if(dep[fx] <= dep[fy])
		{
			T.update(1, dfn[fy], dfn[y], v);
			y = fa[fy];
		}
		else
		{
			T.update(1, dfn[fx], dfn[x], v);
			x = fa[fx];
		}
		fx = top[x];
		fy = top[y];
	}
	T.update(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), v);
	return;
}
inline int qsum(int x, int y)
{
	int ret = 0, fx = top[x], fy = top[y];
	while(fx != fy)
	{
		if(dep[fx] <= dep[fy])
		{
			ret += T.querysum(1, dfn[fy], dfn[y]);
			ret %= p;
			y = fa[fy];
		}
		else
		{
			ret += T.querysum(1, dfn[fx], dfn[x]);
			ret %= p;
			x = fa[fx];
		}
		fx = top[x];
		fy = top[y];
	}
	ret += T.querysum(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]));
	ret %= p;
	return ret;
}
signed main()
{
	int x, y;
	scanf("%lld%lld%lld%lld", &n, &m, &r, &p);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &num[i]);
	}
	for(int i = 1; i < n; i++)
	{
		scanf("%lld%lld", &x, &y);
		add(x, y);
		add(y, x);
	}
	dep[r] = 1;
	dfs1(r);
	dfs2(r, r);
	T.build(1, 1, n);
	int opt, z;
	for(int i = 1; i <= m; i++)
	{
		scanf("%lld", &opt);
		if(opt == 1)
		{
			scanf("%lld%lld%lld", &x, &y, &z);
			addline(x, y, z);
		}
		else if(opt == 2)
		{
			scanf("%lld%lld", &x, &y);
			printf("%lld\n", qsum(x, y));
		}
		else if(opt == 3)
		{
			scanf("%lld%lld", &x, &y);
			T.update(1, dfn[x], dfn[x] + size[x] - 1, y);
		}
		else if(opt == 4)
		{
			scanf("%lld", &x);
			printf("%lld\n", T.querysum(1, dfn[x], dfn[x] + size[x] - 1));
		}
	}
	return 0;
}

Luogu P2590

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define N 30005
int num[N];
int first[N << 1], Next[N << 1], to[N << 1], tot;
inline void add(int x, int y)
{
	Next[++tot] = first[x];
	first[x] = tot;
	to[tot] = y;
	return;
}
int fa[N], dep[N], size[N], hson[N];
void dfs1(int u)
{
	size[u] = 1;
	for(int i = first[u]; i; i = Next[i])
	{
		int v = to[i];
		if(dep[v])
		{
			continue;
		}
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs1(v);
		size[u] += size[v];
		if(!hson[u] || (size[v] > size[hson[u]]))
		{
			hson[u] = v;
		}
	}
	return;
}
int top[N], dfn[N], rnk[N], sign;
void dfs2(int u, int fr)
{
	top[u] = fr;
	dfn[u] = ++sign;
	rnk[sign] = u;
	if(!hson[u])
	{
		return;
	}
	dfs2(hson[u], fr);
	for(int i = first[u]; i; i = Next[i])
	{
		int v = to[i];
		if(v == fa[u] || v == hson[u])
		{
			continue;
		}
		dfs2(v, v);
	}
	return;
}
class segment_tree
{
	private:
	struct node
	{
		int l, r, sum, maxx, tag;
	};
	node tree[N << 2];
	inline void pushup(int root)
	{
		tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
		tree[root].maxx = max(tree[root << 1].maxx, tree[root << 1 | 1].maxx);
		return;
	}
	inline void addtag(int root, int v)
	{
		tree[root].tag += v;
		tree[root].sum += (tree[root].r - tree[root].l + 1) * v;
		tree[root].maxx += v;
		return;
	}
	inline void pushdown(int root)
	{
		if(tree[root].tag)
		{
			addtag(root << 1, tree[root].tag);
			addtag(root << 1 | 1, tree[root].tag);
			tree[root].tag = 0;
		}
		return;
	}
	public:
	void build(int root, int l, int r)
	{
		tree[root].l = l;
		tree[root].r = r;
		if(l == r)
		{
			tree[root].sum = tree[root].maxx = num[rnk[l]];
			return;
		}
		int mid = (l + r) >> 1;
		build(root << 1, l, mid);
		build(root << 1 | 1, mid + 1, r);
		pushup(root);
		return;
	}
	void update(int root, int L, int R, int v)
	{
		if(L <= tree[root].l && tree[root].r <= R)
		{
			addtag(root, v);
			return;
		}
		pushdown(root);
		int mid = (tree[root].l + tree[root].r) >> 1;
		if(L <= mid)
		{
			update(root << 1, L, R, v);
		}
		if(mid < R)
		{
			update(root << 1 | 1, L, R, v);
		}
		pushup(root);
		return;
	}
	int querysum(int root, int L, int R)
	{
		if(L <= tree[root].l && tree[root].r <= R)
		{
			return tree[root].sum;
		}
		pushdown(root);
		int mid = (tree[root].l + tree[root].r) >> 1, ret = 0;
		if(L <= mid)
		{
			ret += querysum(root << 1, L, R);
		}
		if(mid < R)
		{
			ret += querysum(root << 1 | 1, L, R);
		}
		pushup(root);
		return ret;
	}
	int querymax(int root, int L, int R)
	{
		if(L <= tree[root].l && tree[root].r <= R)
		{
			return tree[root].maxx;
		}
		pushdown(root);
		int mid = (tree[root].l + tree[root].r) >> 1, ret = -inf;
		if(L <= mid)
		{
			ret = max(ret, querymax(root << 1, L, R));
		}
		if(mid < R)
		{
			ret = max(ret, querymax(root << 1 | 1, L, R));
		}
		pushup(root);
		return ret;
	}
};
segment_tree T;
inline int qsum(int x, int y)
{
	int ret = 0, fx = top[x], fy = top[y];
	while(fx != fy)
	{
		if(dep[fx] <= dep[fy])
		{
			ret += T.querysum(1, dfn[fy], dfn[y]);
			y = fa[fy];
		}
		else
		{
			ret += T.querysum(1, dfn[fx], dfn[x]);
			x = fa[fx];
		}
		fx = top[x];
		fy = top[y];
	}
	ret += T.querysum(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]));
	return ret;
}
inline int qmax(int x, int y)
{
	int ret = -inf, fx = top[x], fy = top[y];
	while(fx != fy)
	{
		if(dep[fx] <= dep[fy])
		{
			ret = max(ret, T.querymax(1, dfn[fy], dfn[y]));
			y = fa[fy];
		}
		else
		{
			ret = max(ret, T.querymax(1, dfn[fx], dfn[x]));
			x = fa[fx];
		}
		fx = top[x];
		fy = top[y];
	}
	ret = max(ret, T.querymax(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])));
	return ret;
}
int n, q;
char opt[25];
signed main()
{
	int u, v;
	scanf("%lld", &n);
	for(int i = 1; i < n; i++)
	{
		scanf("%lld%lld", &u, &v);
		add(u, v);
		add(v, u);
	}
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &num[i]);
	}
	dep[1] = 1;
	dfs1(1);
	dfs2(1, 1);
	T.build(1, 1, n);
	scanf("%lld", &q);
	for(int i = 1; i <= q; i++)
	{
		scanf("%s%lld%lld", opt, &u, &v);
		if(!strcmp(opt, "CHANGE"))
		{
			T.update(1, dfn[u], dfn[u], v - num[u]);
			num[u] = v;
		}
		else if(!strcmp(opt, "QSUM"))
		{
			printf("%lld\n", qsum(u, v));
		}
		else if(!strcmp(opt, "QMAX"))
		{
			printf("%lld\n", qmax(u, v));
		}
	}
	return 0;
}

Luogu P3178

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
int n, m, num[N], dep[N], in[N], out[N], sign;
int first[N << 1], Next[N << 1], to[N << 1], tot;
inline void add(int x, int y)
{
	Next[++tot] = first[x];
	first[x] = tot;
	to[tot] = y;
	return;
}
void dfs(int u, int pre)
{
	in[u] = ++sign;
	for(int i = first[u]; i; i = Next[i])
	{
		int v = to[i];
		if(v == pre)
		{
			continue;
		}
		dep[v] = dep[u] + 1;
		dfs(v, u);
	}
	out[u] = sign;
	return;
}
class segment_tree
{
	private:
	struct node
	{
		int l, r, val, cnt, tag;
	};
	node tree[N << 2];
	inline void pushup(int root)
	{
		tree[root].val = tree[root << 1].val + tree[root << 1 | 1].val;
		return;
	}
	inline void addtag(int root, int x, int y)
	{
		tree[root].tag += x;
		tree[root].cnt += y;
		tree[root].val += (tree[root].r - tree[root].l + 1) * x;
		return;
	}
	inline void pushdown(int root)
	{
		if(tree[root].tag)
		{
			addtag(root << 1, tree[root].tag, tree[root].cnt);
			addtag(root << 1 | 1, tree[root].tag, tree[root].cnt);
			tree[root].tag = 0;
			tree[root].cnt = 0;
		}
		return;
	}
	public:
	void build(int root, int l, int r)
	{
		tree[root].l = l;
		tree[root].r = r;
		if(l == r)
		{
			tree[root].val = num[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(root << 1, l, mid);
		build(root << 1 | 1, mid + 1, r);
		pushup(root);
		return;
	}
	void update(int root, int L, int R, int x, int y)
	{
		if(L <= tree[root].l && tree[root].r <= R)
		{
			addtag(root, x, y);
			return;
		}
		pushdown(root);
		int mid = (tree[root].l + tree[root].r) >> 1;
		if(L <= mid)
		{
			update(root << 1, L, R, x, y);
		}
		if(mid < R)
		{
			update(root << 1 | 1, L, R, x, y);
		}
		pushup(root);
		return;
	}
	int query(int root, int pos, int val)
	{
		if(tree[root].l == tree[root].r)
		{
			return tree[root].val + val * tree[root].cnt;
		}
		pushdown(root);
		int mid = (tree[root].l + tree[root].r) >> 1;
		if(pos <= mid)
		{
			return query(root << 1, pos, val);
		}
		return query(root << 1 | 1, pos, val);
	}
};
segment_tree tval;
signed main()
{
	int u, v;
	scanf("%lld%lld", &n, &m);
	tval.build(1, 1, n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &num[i]);
	}
	for(int i = 1; i < n; i++)
	{
		scanf("%lld%lld", &u, &v);
		add(u, v);
		add(v, u);
	}
	dep[1] = 1;
	dfs(1, 0);
	for(int i = 1; i <= n; i++)
	{
		tval.update(1, in[i], out[i], num[i], 0);
	}
	int opt, x, y;
	for(int i = 1; i <= m; i++)
	{
		scanf("%lld", &opt);
		if(opt == 1)
		{
			scanf("%lld%lld", &x, &y);
			tval.update(1, in[x], out[x], y, 0);
		}
		else if(opt == 2)
		{
			scanf("%lld%lld", &x, &y);
			tval.update(1, in[x], out[x], -y * dep[x], y);
		}
		else if(opt == 3)
		{
			scanf("%lld", &x);
			printf("%lld\n", tval.query(1, in[x], dep[x] + 1));
		}
	}
	return 0;
}

现在是一些进阶操作：
Woj #4632

这题仔细观察会发现题目中的 f1，f2 都是有意义的，具体的：

讲人话就是 $f1[u]$ 表示这样一个最大值，$f2[u]$ 就是最大值的个数。线段树维护即可。（这道题我是爆搜过的）。
Luogu P2486
这道题就是用线段树维护区间的左端点颜色，右端点颜色，以及当前区间的不同颜色数量。可以定义结构体然后重载运算符来合并。
注意：线段树查询出来的区间是有序的，该反转就反转（交换左右端点就好）。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
struct color_node
{
	int bg, ed, cnt;
};
color_node operator + (const color_node &a, const color_node &b)
{
	if(!a.cnt)
	{
		return b;
	}
	if(!b.cnt)
	{
		return a;
	}
	return (color_node){a.bg, b.ed, a.cnt + b.cnt - (a.ed == b.bg)};
}
struct node
{
	int l, r, tag;
	color_node val;
};
int first[N << 1], Next[N << 1], to[N << 1], tot;
inline void add(int x, int y)
{
	Next[++tot] = first[x];
	first[x] = tot;
	to[tot] = y;
	return;
}
int dep[N], fa[N], size[N], hson[N];
void dfs1(int u)
{
	size[u] = 1;
	for(int i = first[u]; i; i = Next[i])
	{
		int v = to[i];
		if(dep[v])
		{
			continue;
		}
		dep[v] = dep[u] + 1;
		fa[v] = u;
		dfs1(v);
		size[u] += size[v];
		if(!hson[u] || size[hson[u]] < size[v])
		{
			hson[u] = v;
		}
	}
	return;
}
int dfn[N], top[N], rnk[N], sign;
void dfs2(int u, int fr)
{
	dfn[u] = ++sign;
	top[u] = fr;
	rnk[sign] = u;
	if(!hson[u])
	{
		return;
	}
	dfs2(hson[u], fr);
	for(int i = first[u]; i; i = Next[i])
	{
		int v = to[i];
		if(v == fa[u] || v == hson[u])
		{
			continue;
		}
		dfs2(v, v);
	}
	return;
}
int num[N];
class segment_tree
{
	private:
	node tree[N << 2];
	inline void pushup(int root)
	{
		tree[root].val = tree[root << 1].val + tree[root << 1 | 1].val;
		return;
	}
	inline void addtag(int root, int c)
	{
		tree[root].tag = c;
		tree[root].val = (color_node){c, c, 1};
		return;
	}
	inline void pushdown(int root)
	{
		if(tree[root].tag)
		{
			addtag(root << 1, tree[root].tag);
			addtag(root << 1 | 1, tree[root].tag);
			tree[root].tag = 0;
		}
		return;
	}
	public:
	void build(int root, int l, int r)
	{
		tree[root].l = l;
		tree[root].r = r;
		if(l == r)
		{
			tree[root].val = (color_node){num[rnk[l]], num[rnk[l]], 1};
			return;
		}
		int mid = (l + r) >> 1;
		build(root << 1, l, mid);
		build(root << 1 | 1, mid + 1, r);
		pushup(root);
		return;
	}
	void update(int root, int L, int R, int c)
	{
		if(L <= tree[root].l && tree[root].r <= R)
		{
			addtag(root, c);
			return;
		}
		pushdown(root);
		int mid = (tree[root].l + tree[root].r) >> 1;
		if(L <= mid)
		{
			update(root << 1, L, R, c);
		}
		if(mid < R)
		{
			update(root << 1 | 1, L, R, c);
		}
		pushup(root);
		return;
	}
	color_node query(int root, int L, int R)
	{
		if(L <= tree[root].l && tree[root].r <= R)
		{
			return tree[root].val;
		}
		pushdown(root);
		int mid = (tree[root].l + tree[root].r) >> 1;
		color_node ret = (color_node){0, 0, 0};
		if(L <= mid)
		{
			ret = ret + query(root << 1, L, R);
		}
		if(mid < R)
		{
			ret = ret + query(root << 1 | 1, L, R);
		}
		return ret;
	}
};
segment_tree T;
inline void update(int x, int y, int c)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] > dep[top[y]])
		{
			swap(x, y);
		}
		T.update(1, dfn[top[y]], dfn[y], c);
		y = fa[top[y]];
	}
	T.update(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), c);
	return;
}
inline color_node rev(color_node x)
{
	swap(x.bg, x.ed);
	return x;
}
inline color_node query(int x, int y)
{
	color_node retx = (color_node){0, 0, 0}, rety = (color_node){0, 0, 0};
	int fx = top[x], fy = top[y];
	while(fx != fy)
	{
		if(dep[fx] <= dep[fy])
		{
			rety = rety + rev(T.query(1, dfn[fy], dfn[y]));
			y = fa[fy];
		}
		else
		{
			retx = retx + rev(T.query(1, dfn[fx], dfn[x]));
			x = fa[fx];
		}
		fx = top[x];
		fy = top[y];
	}
	rety = rev(rety);
	if(dfn[x] < dfn[y])
	{
		return retx + T.query(1, dfn[x], dfn[y]) + rety;
	}
	else
	{
		return retx + rev(T.query(1, dfn[y], dfn[x])) + rety;
	}
}
int n, m;
signed main()
{
	int x, y, z;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &num[i]);
	}
	for(int i = 1; i < n; i++)
	{
		scanf("%d%d", &x, &y);
		add(x, y);
		add(y, x);
	}
	dep[1] = 1;
	dfs1(1);
	dfs2(1, 1);
	T.build(1, 1, n);
	char op[5];
	for(int i = 1; i <= m; i++)
	{
		scanf("%s", op);
		if(op[0] == 'C')
		{
			scanf("%d%d%d", &x, &y, &z);
			update(x, y, z);
		}
		else if(op[0] == 'Q')
		{
			scanf("%d%d", &x, &y);
			printf("%d\n", query(x, y).cnt);
		}
	}
	return 0;
}

Luogu P7735
这道题最关键的是将这个轻重边的切换操作和重边的统计转化为连续相同颜色的个数。
相当于统计时修改的链只有中间的能算为重边，对于链上的点出去的分叉就可以消除影响。
然后就转化为前一题的做法（今天晚上写这道题的时候状态出奇的好，写完就过样例并 AC 了）。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline void read(int &x)
{
	x = 0;
	int f = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		f |= ch == '-';
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	x = f ? -x : x;
	return;
}
#define N 100005
int first[N << 1], Next[N << 1], to[N << 1], tot;
inline void add(int x, int y)
{
	Next[++tot] = first[x];
	first[x] = tot;
	to[tot] = y;
	return;
}
int fa[N], size[N], dep[N], hson[N];
void dfs1(int u)
{
	size[u] = 1;
	for(int i = first[u]; i; i = Next[i])
	{
		int v = to[i];
		if(dep[v])
		{
			continue;
		}
		dep[v] = dep[u] + 1;
		fa[v] = u;
		dfs1(v);
		size[u] += size[v];
		if(!hson[u] || size[hson[u]] < size[v])
		{
			hson[u] = v;
		}
	}
	return;
}
int dfn[N], top[N], sign;
void dfs2(int u, int fr)
{
	dfn[u] = ++sign;
	top[u] = fr;
	if(!hson[u])
	{
		return;
	}
	dfs2(hson[u], fr);
	for(int i = first[u]; i; i = Next[i])
	{
		int v = to[i];
		if(v == fa[u] || v == hson[u])
		{
			continue;
		}
		dfs2(v, v);
	}
	return;
}
struct node
{
	int val, lcol, rcol;
};
node operator + (const node &a, const node &b)
{
	if(!a.lcol)
	{
		return b;
	}
	if(!b.lcol)
	{
		return a;
	}
	return (node){a.val + b.val + (a.rcol == b.lcol), a.lcol, b.rcol};
}
class segment_tree
{
	public:
	node tree[N << 2];
	int tag[N << 2], l[N << 2], r[N << 2];
	inline void pushup(int root)
	{
		tree[root] = tree[root << 1] + tree[root << 1 | 1];
		return;
	}
	inline void addtag(int root, int c)
	{
		tag[root] = c;
		tree[root] = (node){r[root] - l[root], c, c};
		return;
	}
	inline void pushdown(int root)
	{
		if(tag[root])
		{
			addtag(root << 1, tag[root]);
			addtag(root << 1 | 1, tag[root]);
			tag[root] = 0;
		}
		return;
	}
	void build(int root, int L, int R)
	{
		l[root] = L;
		r[root] = R;
		tree[root] = (node){0, 0, 0};
		tag[root] = 0;
		if(L == R)
		{
			return;
		}
		int mid = (L + R) >> 1;
		build(root << 1, L, mid);
		build(root << 1 | 1, mid + 1, R);
		//pushup(root);
		return;
	}
	void update(int root, int L, int R, int c)
	{
		if(L <= l[root] && r[root] <= R)
		{
			addtag(root, c);
			return;
		}
		pushdown(root);
		int mid = (l[root] + r[root]) >> 1;
		if(L <= mid)
		{
			update(root << 1, L, R, c);
		}
		if(mid < R)
		{
			update(root << 1 | 1, L, R, c);
		}
		pushup(root);
		return;
	}
	node query(int root, int L, int R)
	{
		if(L <= l[root] && r[root] <= R)
		{
			return tree[root];
		}
		pushdown(root);
		int mid = (l[root] + r[root]) >> 1;
		node ret = (node){0, 0, 0};
		if(L <= mid)
		{
			ret = ret + query(root << 1, L, R);
		}
		if(mid < R)
		{
			ret = ret + query(root << 1 | 1, L, R);
		}
		return ret;
	}
};
segment_tree T;
int cnt;
inline void update(int x, int y, int c)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] > dep[top[y]])
		{
			swap(x, y);
		}
		T.update(1, dfn[top[y]], dfn[y], c);
		y = fa[top[y]];
	}
	T.update(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), c);
	return;
}
inline node rev(node x)
{
	swap(x.lcol, x.rcol);
	return x;
}
inline node query(int x, int y)
{
	node retx = (node){0, 0, 0}, rety = (node){0, 0, 0};
	int fx = top[x], fy = top[y];
	while(fx != fy)
	{
		if(dep[fx] <= dep[fy])
		{
			rety = rety + rev(T.query(1, dfn[fy], dfn[y]));
			y = fa[fy];
		}
		else
		{
			retx = retx + rev(T.query(1, dfn[fx], dfn[x]));
			x = fa[fx];
		}
		fx = top[x];
		fy = top[y];
	}
	rety = rev(rety);
	if(dfn[x] < dfn[y])
	{
		return retx + T.query(1, dfn[x], dfn[y]) + rety;
	}
	else
	{
		return retx + rev(T.query(1, dfn[y], dfn[x])) + rety;
	}
}
inline void init()
{
	tot = sign = cnt = 0;
	memset(first, 0, sizeof(first));
	//memset(fa, 0, sizeof(fa));
	//memset(size, 0, sizeof(size));
	memset(dep, 0, sizeof(dep));
	memset(hson, 0, sizeof(hson));
	//memset(dfn, 0, sizeof(dfn));
	//memset(top, 0, sizeof(top));
	return;
}
int n, m;
signed main()
{
	int Case, opt, u, v;
	read(Case);
	while(Case--)
	{
		init();
		read(n), read(m);
		for(int i = 1; i < n; i++)
		{
			read(u), read(v);
			add(u, v);
			add(v, u);
		}
		dep[1] = 1;
		dfs1(1);
		dfs2(1, 1);
		T.build(1, 1, n);
		for(int i = 1; i <= m; i++)
		{
			read(opt), read(u), read(v);
			if(opt == 1)
			{
				update(u, v, ++cnt);
			}
			else
			{
				printf("%d\n", query(u, v).val);
			}
		}
	}
	return 0;
}