Acyclic Organic Compounds

题意：

给一以1为根的字符树，给出每个节点的字符与权值，记 $diff_{x}$ 为从 $x$ 出发向下走，能走到多少不同的字符串，求问最大的
$diff_{x} + c_{x}$，并求有多少个 $diff_{x} + c_{x}$。

解法：

考虑$dfs$，从下到上启发式合并 $Trie$ 树，效率 $O(nlogn)$。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define N 300010

 using namespace std;

 struct edge

 {

     int x,to;

 }E[N<<];

 struct node

 {

     node *ch[];

     int siz;

     node* init()

     {

         siz=;

         memset(ch,,sizeof(ch));

         return this;

     };

 }spT[N<<],*root[N];

 int n,m,totn,totE,ans,ansv;

 int fa[N],g[N],c[N];

 char S[N];

 void addedge(int x,int y)

 {

     E[++totE] = (edge){y,g[x]}; g[x]=totE;

     E[++totE] = (edge){x,g[y]}; g[y]=totE;

 }

 #define p E[i].x

 node* merge(node *p1,node *p2)

 {

     if(p1->siz < p2->siz) swap(p1,p2);

     for(int t=;t<;t++)

         if(p2->ch[t])

         {

             if(!p1->ch[t]) p1->ch[t]=p2->ch[t];

             else p1->ch[t] = merge(p1->ch[t], p2->ch[t]);

         }

     p1->siz=;

     for(int t=;t<;t++)

         if(p1->ch[t]) p1->siz+=p1->ch[t]->siz;

     return p1;

 }

 void dfs(int x)

 {

     int tmp=S[x]-'a';

     root[x]=spT[++totn].init();

     root[x]->ch[tmp]=spT[++totn].init();

     for(int i=g[x];i;i=E[i].to)

         if(p!=fa[x])

         {

             fa[p]=x;

             dfs(p);

         }

     for(int i=g[x];i;i=E[i].to)

         if(p!=fa[x])

             root[x]->ch[tmp] = merge(root[x]->ch[tmp],root[p]);

     root[x]->siz = root[x]->ch[tmp]->siz;

     if(root[x]->siz+c[x] > ansv)

     {

         ansv = root[x]->siz+c[x];

         ans=;

     }

     else if(root[x]->siz+c[x] == ansv) ans++;

 }

 int main()

 {

     while(~scanf("%d",&n))

     {

         for(int i=;i<=n;i++) g[i]=;

         totE=;

         for(int i=;i<=n;i++) scanf("%d",&c[i]);

         S[]='*';

         scanf("%s",S+);

         ans=;

         totn=ansv=;

         for(int i=,x,y;i<n;i++)

         {

             scanf("%d%d",&x,&y);

             addedge(x,y);

         }

         fa[]=;

         dfs();

         cout << ansv << endl << ans << endl;

     }

     return ;

 }