n<=100000的树，每个点上有个字母a-t之一，问有多少这样的链经过每个点：它的某一个排列的字母串起来是回文的。
就是有最多一个字母是奇数个啦。。这样点分算一波即可。。细节较多详见代码
1 #include<string.h> 2 #include<stdlib.h> 3 #include<stdio.h> 4 #include<math.h> 5 #include<algorithm> 6 //#include<queue> 7 //#include<iostream> 8 using namespace std; 9 10 int n; 11 #define maxn 200011 12 struct Edge{int to,next;}edge[maxn<<1]; int first[maxn],le=2,val[maxn]; char s[maxn]; 13 void in(int x,int y) {Edge &e=edge[le]; e.to=y; e.next=first[x]; first[x]=le++;} 14 void insert(int x,int y) {in(x,y); in(y,x);} 15 16 #define maxs 1111111 17 int cnt[maxs]; 18 19 #define LL long long 20 LL ans[maxn]; int size[maxn]; bool die[maxn]; 21 void getsize(int x,int fa) 22 { 23 size[x]=1; 24 for (int i=first[x];i;i=edge[i].next) 25 { 26 const Edge &e=edge[i]; if (e.to==fa || die[e.to]) continue; 27 getsize(e.to,x); size[x]+=size[e.to]; 28 } 29 } 30 31 int getroot(int x,int fa,int tot) 32 { 33 for (int i=first[x];i;i=edge[i].next) 34 { 35 const Edge &e=edge[i]; if (e.to==fa || die[e.to]) continue; 36 if (size[e.to]*2>tot) return getroot(e.to,x,tot); 37 } 38 return x; 39 } 40 41 void dfscnt(int x,int fa,int now,int v) 42 { 43 now^=1<<val[x]; cnt[now]+=v; 44 for (int i=first[x];i;i=edge[i].next) 45 { 46 const Edge &e=edge[i]; if (e.to==fa || die[e.to]) continue; 47 dfscnt(e.to,x,now,v); 48 } 49 } 50 51 LL calc(int x,int fa,int now) 52 { 53 now^=1<<val[x]; LL t=0; 54 for (int i=0;i<20;i++) t+=cnt[now^(1<<i)]; 55 t+=cnt[now]; 56 for (int i=first[x];i;i=edge[i].next) 57 { 58 const Edge &e=edge[i]; if (e.to==fa || die[e.to]) continue; 59 t+=calc(e.to,x,now); 60 } 61 ans[x]+=t; return t; 62 } 63 64 void cd(int x) 65 { 66 dfscnt(x,0,0,1); die[x]=1; 67 LL now=0; 68 for (int i=first[x];i;i=edge[i].next) 69 { 70 const Edge &e=edge[i]; if (die[e.to]) continue; 71 dfscnt(e.to,x,1<<val[x],-1); 72 now+=calc(e.to,x,0); //cout<<e.to<<' '<<now<<endl; 73 dfscnt(e.to,x,1<<val[x],1); 74 } 75 76 for (int i=0;i<20;i++) now+=cnt[1<<i]; 77 now+=cnt[0]+1; ans[x]+=now>>1; 78 dfscnt(x,0,0,-1); 79 // cout<<x<<endl; 80 // for (int i=1;i<=n;i++) cout<<ans[i]<<' ';cout<<endl; 81 for (int i=first[x];i;i=edge[i].next) 82 { 83 const Edge &e=edge[i]; if (die[e.to]) continue; 84 getsize(e.to,0); cd(getroot(e.to,0,size[e.to])); 85 } 86 } 87 88 int main() 89 { 90 scanf("%d",&n); 91 for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),insert(x,y); 92 scanf("%s",s+1); for (int i=1;i<=n;i++) val[i]=s[i]-'a'; 93 getsize(1,0); 94 cd(getroot(1,0,size[1])); 95 for (int i=1;i<=n;i++) printf("%lld ",ans[i]); 96 return 0; 97 }