思维好题
首先考虑哪些状态下所有答案均为0，一种是，对于某一个点的邻边，存在三个相同的数，或者存在aabb形的数，因为我们无论以哪个点为根，这个点一定有两个作为他的儿子，所以上述情况都不满足。
在特判过后，我们寻找哪些可能满足条件，考虑进行dfs序遍历，对于每个点的dfs序和在他邻边中两个相等的边所连的点的dfs进行比较后，利用线段树把非法区间都置为1
这样我们查询整个树看看哪些点为0，这些点是可以作为根节点的
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=200005; const int inf=0x3f3f3f3f; int h[N],ne[N],e[N],idx; char w[N]; int dfn[N],times; struct node{ int l,r; int sum; int lazy; }tr[N<<2]; int sz[N],n; void add(int a,int b,char c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } bool solve(int u){ int i; int cnt[27]={0}; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; cnt[w[i]-'a']++; } int flag=0; for(i=0;i<26;i++){ if(cnt[i]>2){ return false; } if(cnt[i]==2){ if(flag) return false; flag++; } } return true; } bool check(){ int i; for(i=1;i<=n;i++){ if(!solve(i)) return false; } return true; } void dfs(int u,int fa){ dfn[u]=++times; int i; sz[u]=1; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==fa) continue; dfs(j,u); sz[u]+=sz[j]; } } void build(int u,int l,int r){ if(l==r){ tr[u]={l,r,0,0}; } else{ tr[u]={l,r,0,0}; int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); } } void pushup(int u){ tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; } void pushdown(int u){ int x=tr[u].lazy; tr[u<<1].sum=(tr[u<<1].r-tr[u<<1].l+1); tr[u<<1|1].sum=(tr[u<<1|1].r-tr[u<<1|1].l+1); tr[u<<1].lazy=tr[u<<1|1].lazy=x; tr[u].lazy=0; } void modify(int u,int l,int r,int k){ if(tr[u].l>=l&&tr[u].r<=r){ tr[u].sum=k*(tr[u].r-tr[u].l+1); tr[u].lazy=k; return ; } if(tr[u].lazy) pushdown(u); int mid=tr[u].l+tr[u].r>>1; if(l<=mid) modify(u<<1,l,r,k); if(r>mid) modify(u<<1|1,l,r,k); pushup(u); } int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ cin>>n; int i; idx=0,times=0; for(i=0;i<=n+5;i++){ h[i]=-1; } for(i=1;i<n;i++){ int a,b; char c; cin>>a>>b>>c; add(a,b,c); add(b,a,c); } if(!check()){ cout<<0<<endl; continue; } dfs(1,-1); build(1,1,n); for(i=1;i<=n;i++){ map<char,int> m1; for(int j=h[i];j!=-1;j=ne[j]){ int k=e[j]; if(!m1[w[j]]){ m1[w[j]]=k; continue; } int f1=m1[w[j]]; int f2=k; if(dfn[f1]>dfn[i]&&dfn[f2]>dfn[i]){ if(dfn[f1]>dfn[f2]) swap(f1,f2); modify(1,1,dfn[f1]-1,1); if(dfn[f1]+sz[f1]<=n){ modify(1,dfn[f1]+sz[f1],dfn[f2]-1,1); } if(dfn[f2]+sz[f2]<=n) modify(1,dfn[f2]+sz[f2],n,1); } else if(dfn[f1]>dfn[i]&&dfn[f2]<dfn[i]){ modify(1,dfn[i],dfn[f1]-1,1); if(dfn[f1]+sz[f1]<=n) modify(1,dfn[f1]+sz[f1],dfn[i]+sz[i]-1,1); } else if(dfn[f1]<dfn[i]&&dfn[f2]>dfn[i]){ modify(1,dfn[i],dfn[f2]-1,1); if(dfn[f2]+sz[f2]<=n) modify(1,dfn[f2]+sz[f2],dfn[i]+sz[i]-1,1); } break; } } cout<<n-tr[1].sum<<endl; } return 0; }