发现不满足题意的情况就是一个节点到多个子节点的边的字母相同，那么合法当且仅当每个节点到子节点的字母互不相同。那么可以统计每个节点连接的字母数量，并运用类似换根 dp 的思路，快速更新这个数量并实时维护符合条件的点的数量即可。时间复杂度 \(O(nA)\)，其中 \(A=26\) 为字符集大小。
#include<iostream>
#include<cstdio>
#define N 200010
using namespace std;
struct E{int v,nxt;int w;
}e[N*2];
int n,a[N][26],tot,hd[N],cnt,ans;
bool flag[N];
void add(int u,int v,char w){tot++;e[tot].v=v,e[tot].w=w-'a',e[tot].nxt=hd[u];hd[u]=tot;
}
bool ck(int u){for(int i=0;i<26;i++)if(a[u][i]>1)return false;return true;
}
void dfs1(int u,int fa){for(int i=hd[u];i;i=e[i].nxt){int v=e[i].v,w=e[i].w;if(v==fa)continue;a[u][w]++;dfs1(v,u);}cnt+=ck(u);
}
void dfs2(int u,int fa){if(cnt==n)ans++;for(int i=hd[u];i;i=e[i].nxt){int v=e[i].v,w=e[i].w;if(v==fa)continue;cnt-=ck(u),cnt-=ck(v);a[u][w]--,a[v][w]++;cnt+=ck(u),cnt+=ck(v);dfs2(v,u);cnt-=ck(u),cnt-=ck(v);a[u][w]++,a[v][w]--;cnt+=ck(u),cnt+=ck(v);}
}
void solve(){int u,v;char w;cin>>n;for(int i=1;i<=n;i++){hd[i]=0;for(int j=0;j<26;j++)a[i][j]=0;}tot=0;for(int i=1;i<n;i++){cin>>u>>v>>w;add(u,v,w);add(v,u,w);}cnt=ans=0;dfs1(1,0);dfs2(1,0);cout<<ans<<'\n';return;
}
int main(){int T;cin>>T;while(T--)solve();return 0;
}