11-20 TLE 1.20s
Record

#include <iostream>
#include <vector>
#define ls(x) x << 1
#define rs(x) x << 1 | 1

using namespace std;

int n, m;
struct Node
{
	int l, r, ans, lt;
	Node (int _l = 0, int _r = 0, int _ans = 0) { l = _l, r = _r, ans = _ans; }
};

namespace SGT
{
	Node tree[500001];
	
	Node Merge(Node a, Node b)
	{
		int _ans = a.ans + b.ans;
		if (a.r == b.l) _ans++;
		return Node(a.l, b.r, _ans);
	}
	
	inline void Pushup(int cur)
	{
		tree[cur] = Merge(tree[ls(cur)], tree[rs(cur)]);
	}
	
	void Build(int l, int r, int cur)
	{
		tree[cur].lt = 0;
		if (l == r)
		{
			tree[cur].l = tree[cur].r = 0;
			tree[cur].ans = 0;
			return;
		}
		int mid = (l + r) >> 1;
		Build(l, mid, ls(cur));
		Build(mid + 1, r, rs(cur));
	}
	
	inline void Pushdown(int cur, int s, int t)
	{
		tree[ls(cur)].lt = tree[rs(cur)].lt = tree[cur].lt;
		tree[ls(cur)].l = tree[ls(cur)].r = tree[rs(cur)].l = tree[rs(cur)].r = tree[cur].lt;
		int mid = (s + t) >> 1;
		tree[ls(cur)].ans = mid - s, tree[rs(cur)].ans = t - mid - 1;
		tree[cur].lt = 0;
	}
	
	void Update(int l, int r, int s, int t, int cur, int x)
	{
		if (l <= s && t <= r)
		{
			tree[cur].l = tree[cur].r = x;
			tree[cur].lt = x;
			tree[cur].ans = t - s;
			return;
		}
		if (tree[cur].lt) Pushdown(cur, s, t);
		int mid = (s + t) >> 1;
		if (l <= mid) Update(l, r, s, mid, ls(cur), x);
		if (r > mid) Update(l, r, mid + 1, t, rs(cur), x);
		Pushup(cur);
	}
	
	Node Query(int l, int r, int s, int t, int cur)
	{
		if (l <= s && t <= r) return tree[cur];
		if (tree[cur].lt) Pushdown(cur, s, t);
		int mid = (s + t) >> 1;
		Node ans;
		bool flag = false;
		if (l <= mid) ans = Query(l, r, s, mid, ls(cur)), flag = true;
		if (r > mid)
		{
			Node ar = Query(l, r, mid + 1, t, rs(cur));
			if (flag) ans = Merge(ans, ar);
			else ans = ar;
		}
		return ans;
	}
	
}
	
namespace TCS
{
	vector <int> adj[100005];
	int fa[100005], siz[100005], dep[100001], hson[100005], dfn[100005], rnk[100005], top[100005];
	int cnt = 0;
	
	inline void Reset()
	{
		for (int i = 1; i <= n; i++)
		{
			adj[i].clear();
			fa[i] = 0;
			cnt = 0;
			dep[i] = 0;
			hson[i] = 0;
		}
	}
	
	inline void AddEdge(int u, int v)
	{
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	void DFS1(int cur)
	{
		siz[cur] = 1;
		for (auto it : adj[cur])
		{
			if (it == fa[cur]) continue;
			dep[it] = dep[cur] + 1;
			fa[it] = cur;
			DFS1(it);
			siz[cur] += siz[it];
			if (!hson[cur] || siz[cur] > siz[hson[cur]]) hson[cur] = it;
		}
	}
	
	void DFS2(int cur, int head)
	{
		top[cur] = head;
		dfn[cur] = ++cnt;
		rnk[cnt] = cur;
		if (!hson[cur]) return;
		DFS2(hson[cur], head);
		for (auto it : adj[cur])
		{
			if (it != hson[cur] && it != fa[cur]) DFS2(it, it);
		}
	}
	
	void Update(int u, int v, int x)
	{
		while (top[u] != top[v])
		{
			if (dep[top[u]] < dep[top[v]]) swap(u, v);
			SGT :: Update(dfn[top[u]], dfn[u], 1, n, 1, x);
			u = fa[top[u]];
		}
		if (dep[u] > dep[v]) swap(u, v);
		SGT :: Update(dfn[u], dfn[v], 1, n, 1, x);
	}
	
	int Query(int u, int v)
	{
		Node ansu, ansv, tmp;
		int ans = 0;
		bool flagu = false, flagv = false;
		while (top[u] != top[v])
		{
			if (dep[top[u]] < dep[top[v]])
			{
				tmp = SGT :: Query(dfn[top[v]], dfn[v], 1, n, 1);
				if (!flagv) ansv = tmp, flagv = true;
				else ansv = SGT :: Merge(tmp, ansv);
				v = fa[top[v]];
			}	
			else
			{
				tmp = SGT :: Query(dfn[top[u]], dfn[u], 1, n, 1);
				if (!flagu) ansu = tmp, flagu = true;
				else ansu = SGT :: Merge(tmp, ansu);
				u = fa[top[u]];
			}
		}
		if (dep[u] < dep[v])
		{
			tmp = SGT :: Query(dfn[u], dfn[v], 1, n, 1);
			if (!flagv) ansv = tmp, flagv = true;
			else ansv = SGT :: Merge(tmp, ansv);
			if (!flagu) ans = ansv.ans;
			else ans = ansu.ans + ansv.ans + (ansu.l == ansv.l);
		}
		else
		{
			tmp = SGT :: Query(dfn[v], dfn[u], 1, n, 1);
			if (!flagu) ansu = tmp, flagu = true;
			else ansu = SGT :: Merge(tmp, ansu);
			if (!flagv) ans = ansu.ans;
			else ans = ansu.ans + ansv.ans + (ansu.l == ansv.l);
		}
		return ans;
	}
	
	void Debug(int i)
	{
		cout << dep[i] << ' ' << fa[i] << ' ' << hson[i] << ' ' << top[i] << ' ' << siz[i] << ' ' << dfn[i] << endl;
	}
}


void Solve()
{
	scanf("%d%d", &n, &m);
	int u, v, mode;
	TCS :: Reset();
	for (int i = 1; i < n; i++) 
	{
		scanf("%d%d", &u, &v);
		TCS :: AddEdge(u, v);
	}
	TCS :: DFS1(1);
	TCS :: DFS2(1, 1);
	SGT :: Build(1, n, 1);
	for (int i = 1; i <= n; i++) TCS :: Update(i, i, - i - 1);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &mode, &u, &v);
		if (mode == 1) TCS :: Update(u, v, i);
		else printf("%d\n", TCS :: Query(u, v));
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--) Solve();
	return 0;
}

可能树剖写假了，但我一直没找到错，求大佬帮忙！