upd 2026.7.15 修改了一处笔误。

思路

我们将边权下放到子节点做点权，再 DFS 跑出欧拉序。
那么我们就把树上问题搬到了序列上。
问题转化就成了：

• 单点改权值。
• 统计区间出现次数为奇数次的点的点权种类数。

带修莫队就可以解决。
取 $n,m$ 同阶，因为左端点固定，所以只用移动右端点和时间轴，莫队块长取 $\sqrt n$，时间复杂度 $O(n \sqrt n)$。

实现要注意一些小细节：

1. 欧拉序要在每个点进出各记录一次，数组大小要开两倍。
2. 因为下放到点权，所以根节点的权值为 $0$，会被统计在内，所以答案需要减一。

:::success[代码]{open}

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1.5e5+5;
struct node{
	int r,id,t;//右端点，编号，时间
}w[N];//询问 
struct xx{
	int w,e,o;//位置，新值，旧值 
}h[N];//修改 
int n,m,c,q,g,B,a[N],aa[N];
int dfn[N*2],cnt,fa[N],in[N];
int p[N],sum,vis[N],ans[N];
vector<pair<int,int> > d[N];//邻接表
pair<int,int> b[N];//记录边 
inline bool cmp(node x,node y){
	return (x.r/B==y.r/B?x.t<y.t:x.r<y.r);
}
inline void dfs(int x){
	in[x]=++cnt;//进入时的序号 
	dfn[cnt]=x;//欧拉序 
	for(auto y:d[x]){
		if(y.fi==fa[x]) continue;
		fa[y.fi]=x;
		aa[y.fi]=a[y.fi]=y.se;//下放做点权 
		dfs(y.fi);
	}
	dfn[++cnt]=x;//欧拉序 
}
inline void change(int x){//移动右端点 
	vis[x]^=1;//改变奇偶性 
	if( vis[x]){if(!p[a[x]]) sum++;p[a[x]]++;}
	if(!vis[x]){p[a[x]]--;if(!p[a[x]]) sum--;}
}
inline void updata(int t,bool f){//移动时间轴 
	int x=h[t].w,y=(f?h[t].e:h[t].o);
	if(!vis[x]){a[x]=y;return;}
	p[a[x]]--;if(!p[a[x]]) sum--;
	a[x]=y;
	if(!p[a[x]]) sum++;p[a[x]]++;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> c >> m;
	B=sqrt(n);
	for(int i=1;i<n;i++){
		int x,y,z;
		cin >> x >> y >> z;
		b[i]={x,y};
		d[x].push_back({y,z});
		d[y].push_back({x,z});
	}
	dfs(1);
	for(int i=1;i<=m;i++){
		int l,r;
		char op;
		cin >> op >> l;
		if(op=='Z') ++q,w[q]={in[l],q,g};
		else{
			cin >> r;
			l=(fa[b[l].fi]==b[l].se?b[l].fi:b[l].se);//找子节点 
			h[++g]={l,r,aa[l]};
			aa[l]=r;
		}
	}
	sort(w+1,w+q+1,cmp);
	for(int j=1;j<=w[1].r;j++) change(dfn[j]);//右移右端点 
	for(int j=1;j<=w[1].t;j++) updata(j,1);//增加时间轴 
	ans[w[1].id]=sum-1;
	for(int i=2;i<=q;i++){
		for(int j=w[i-1].r+1;j<=w[i].r;j++) change(dfn[j]);//右移右端点 
		for(int j=w[i-1].r;j>=w[i].r+1;j--) change(dfn[j]);//左移右端点 
		for(int j=w[i-1].t+1;j<=w[i].t;j++) updata(j,1);//增加时间轴 
		for(int j=w[i-1].t;j>w[i].t;j--) updata(j,0);//减少时间轴 
		ans[w[i].id]=sum-1;
	}
	for(int i=1;i<=q;i++) cout << ans[i] << '\n';
	return 0;
}

:::