题解：P9295 [POI 2020] Gang Biciaków / 布茨帮

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+100,M = 1.5e5+1;
namespace  rorrurorror
{
	const int MAXBUF=1<<20;
	char buf[MAXBUF],*p1=buf,*p2=buf;
	char pbuf[MAXBUF],*pp=pbuf;
	inline char getc(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,MAXBUF,stdin),p1==p2)?EOF:*p1++;}
	inline void ri(int &x){x=0;char c=getc();while(!isdigit(c))c=getc();while(isdigit(c))x=x*10+(c^48),c=getc();}
	inline void putc(char c){(pp==pbuf+MAXBUF)&&(fwrite(pbuf,1,MAXBUF,stdout),pp=pbuf),*pp++=c;}
	inline void print_final(){fwrite(pbuf,1,pp-pbuf,stdout),pp=pbuf;}
	inline void wi(int x){if(x>9)wi(x/10);putc(x%10^48);}
}
using rorrurorror::ri;
using rorrurorror::wi;
using rorrurorror::getc;
using rorrurorror::putc;
using rorrurorror::print_final;
struct edge{int t,w,pos;};
vector<edge> a[N];
int n,m,qq;
bool key[N],tt[M];
int cnttmp[M],dep[N],mxdep[N],f[N];
int blo,cnt[300][M],ans[N],tot,be[N],rb[N],bg[N],ke[N],ed[N],to[N];
int tmp[N];
inline void dfs0(int x,int fa)
{
	mxdep[x]=dep[x];
	edge i;
	for(int j=0;j<a[x].size();j++)
	{
		i=a[x][j];
		if(i.t==fa)continue;
		f[i.t]=x;
		to[i.t]=i.w;
		ke[i.pos]=i.t;
		dep[i.t]=dep[x]+1;
		dfs0(i.t,x);
		mxdep[x]=max(mxdep[x],mxdep[i.t]);
	}
	if(dep[x]%blo==0&&mxdep[x]-dep[x]>=blo)key[x]=1;
}
inline void dfs(int x,int fa)
{
	bg[x]=tot+1;
	if(key[x])memcpy(cnt[be[x]=++tot],cnttmp,sizeof(int)*(m+1)),rb[tot]=x;
	edge i;
	for(int j=0;j<a[x].size();j++)
	{
		i=a[x][j];
		if(i.t==fa)continue;
		cnttmp[i.w]++;
		ans[i.t]=ans[x];
		if(cnttmp[i.w]==1)ans[i.t]++;
		dfs(i.t,x);
		cnttmp[i.w]--;
	}
	ed[x]=tot;
}
inline int get(int x)
{
	tot=0;
	while(!key[x])
	{
		if(!tt[to[x]])tmp[++tot]=to[x],tt[to[x]]=1;
		x=f[x];
	}
	int res=ans[x];
	for(int i=1;i<=tot;i++)
	{
		if(!cnt[be[x]][tmp[i]])res++;
		tt[tmp[i]]=0;
	}
	return res;
}
inline void ea(int x,int tp)
{
	for(int i=bg[x];i<=ed[x];i++)
	{
		cnt[i][tp]--;
		if(!cnt[i][tp])ans[rb[i]]--;
	}
}
inline void ad(int x,int tp)
{
	for(int i=bg[x];i<=ed[x];i++)
	{
		cnt[i][tp]++;
		if(cnt[i][tp]==1)ans[rb[i]]++;
	}
}
signed main()
{
	ri(n),ri(m),ri(qq);
	blo=sqrt(n)*1.21+1;
	int x,y,z;
	char op;
	for(int i=1;i<n;i++)ri(x),ri(y),ri(z),a[x].push_back({y,z,i}),a[y].push_back({x,z,i});
	dfs0(1,0);
	key[1]=1;
	dfs(1,0);
	while(qq--)
	{
		op=getc();
		while(op!='Z'&&op!='B')op=getc();
		if(op=='Z')
		{
			ri(x);
			get(x);
			wi(get(x)),putc('\n');
		}
		else
		{
			ri(x),ri(y);
			if(y==to[ke[x]])continue;
			ea(ke[x],to[ke[x]]);
			to[ke[x]]=y;
			ad(ke[x],to[ke[x]]);
		}
	}
	print_final();
}