本地测 #1 是对的，可是交上去就是 WA 的，求大佬解答。

Code:

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 1e5 + 10;

struct node{
	int l, r, sum;
	int lc, rc;
};

node merge(node n1, node n2){
	if(n1.l == 0)return n2;
	if(n2.l == 0)return n1;
	node ret;
	ret.l = n1.l; ret.r = n2.r;
	ret.lc = n1.lc; ret.rc = n2.rc;
	ret.sum = n1.sum + n2.sum + (n1.rc == n2.lc);
	return ret;
}

int newcol;
int n, m;
struct edge{
	int v, next;
}edges[N << 1];
int head[N], idx;
void add_edge(int u, int v){
	idx++;
	edges[idx].v = v;
	edges[idx].next = head[u];
	head[u] = idx;
}

int fa[N], dep[N], siz[N], son[N], dfn[N], rev[N], top[N];
void dfs1(int u, int father){
	fa[u] = father;
	dep[u] = dep[father] + 1;
	siz[u] = 1; son[u] = 0;
	for(int i = head[u]; i; i = edges[i].next){
		int v = edges[i].v;
		if(v == father)continue;
		dfs1(v, u);
		if(siz[v] > siz[son[u]]) son[u] = v;
		siz[u] += siz[v];
	}
	return;
}
int dfncnt;
void dfs2(int u, int tp){
	dfn[u] = ++dfncnt;
	rev[dfn[u]] = u;
	top[u] = tp;
	if(son[u]) dfs2(son[u], tp);
	for(int i = head[u]; i; i = edges[i].next){
		int v = edges[i].v;
		if(v != fa[u] && v != son[u])dfs2(v, v);
	}
	return;
}

struct Segment_tree{
	#define ls (o << 1)
	#define rs (o << 1 | 1)
	#define mid (l + r >> 1)
	#define bls (s <= mid)
	#define brs (mid < t)
	int tag[N << 2];
	node tnode[N << 2];
	void pushup(int o){tnode[o] = merge(tnode[ls], tnode[rs]);}
	void pushdown(int o, int l, int r){
		if(!tag[o])return;
		tag[ls] = tag[rs] = tag[o];
		tnode[ls] = {l, mid, mid - l, tag[o], tag[o]};
		tnode[rs] = {mid + 1, r, r - mid - 1, tag[o], tag[o]};
		tag[o] = 0;
	}
	void build(int o, int l, int r){
		tag[o] = 0;
		if(l == r){
			tnode[o] = {l, r, 0, l, l};
			return;
		}
		build(ls, l, mid);
		build(rs, mid + 1, r);
		pushup(o);
	}
	void upd(int o, int l, int r, int s, int t){
		// cout << o << " " << l << " " << r << " " << s << " " << t << "\n";
		if(s <= l && r <= t){
			tnode[o] = {l, r, r - l, newcol, newcol};
			tag[o] = newcol;
			return;
		}
		pushdown(o, l, r);
		if(bls)upd(ls, l, mid, s, t);
		if(brs)upd(rs, mid + 1, r, s, t);
		pushup(o);
	}
	node querynode(int o, int l, int r, int s, int t){
		//cout << l << " " << r << " " << s << " " << t << "\n";
		if(s <= l && r <= t)return tnode[o];
		pushdown(o, l, r);
		node ret;
		if(bls && brs)ret = merge(querynode(ls, l, mid, s, t), querynode(rs, mid + 1, r, s, t));
		else if(bls)ret = querynode(ls, l, mid, s, t);
		else if(brs)ret = querynode(rs, mid + 1, r, s, t);
		//else assert(0);
		pushup(o);
		return ret;
	}
}tr;

void Qtag(int x, int y){
	newcol++;
	while(top[x] != top[y]){
		if(dep[top[x]] > dep[top[y]])tr.upd(1, 1, n, dfn[top[x]], dfn[x]), x = fa[top[x]];
		else tr.upd(1, 1, n, dfn[top[y]], dfn[y]), y = fa[top[y]];
	}
	if(dfn[x] < dfn[y])tr.upd(1, 1, n, dfn[x], dfn[y]);
	else tr.upd(1, 1, n, dfn[y], dfn[x]);
	return;
}
node Qsum(int x, int y){
	node ret1, ret2;
	ret1.l = ret2.l = 0;
	while(top[x] != top[y]){
		if(dep[top[x]] > dep[top[y]])ret1 = merge(tr.querynode(1, 1, n, dfn[top[x]], dfn[x]), ret1), x = fa[top[x]];
		else ret2 = merge(tr.querynode(1, 1, n, dfn[top[y]], dfn[y]), ret2), y = fa[top[y]]; 
	}
	if(dfn[x] > dfn[y])swap(x, y), swap(ret1, ret2);
	swap(ret1.lc, ret1.rc); swap(ret1.l, ret1.r);
	ret1 = merge(ret1, tr.querynode(1, 1, n, dfn[x], dfn[y]));
	return merge(ret1, ret2);
}

signed main(){
	//freopen("1.in", "r", stdin);
	//freopen("1.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T; cin >> T;
	while(T--){
		cin >> n >> m;
		newcol = n; dfncnt = 0;
		for(int i = 1; i <= n; i++) head[i] = 0;
		idx = 0;
		for(int i = 1; i < n; i++){
			int x, y;
			cin >> x >> y;
			add_edge(x, y);
			add_edge(y, x);
		}
		dfs1(1, 0);
		dfs2(1, 1);
		tr.build(1, 1, n);
		while(m--){
			int opt, x, y;
			cin >> opt >> x >> y;
			if(opt == 1) Qtag(x, y);
			if(opt == 2) cout << Qsum(x, y).sum << "\n";
		}
	}
	
	// system("pause");
	return 0;
}