题意:

给一以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 ;
}

最新文章

  1. jsp页面输入小写金额转大写
  2. ubuntu删除输入法后,循环登陆
  3. Customizing the Editor
  4. 转!!java中的内部类总结
  5. ehcache 缓存
  6. socket.io发送给指定的客户端
  7. COM实践经验
  8. POJ 1322 Chocolate
  9. 【数据结构&amp;amp;&amp;amp;等差数列】KMP简介和算法的实现(c++ &amp;amp;&amp;amp; java)
  10. POPTEST老李分享session,cookie的安全性以及区别 3
  11. SSL/TLS通信
  12. Lucene 05 - 使用Lucene的Java API实现分页查询
  13. Rsync未授权访问漏洞的修复
  14. linux 出现ping,错误提示:connect :network is unreachable
  15. whith ~ as 用法
  16. Android_OnLowMemory和OnTrimMemory
  17. 基于qml创建最简单的android机图像采集程序
  18. 清空mailq 队列里面的邮件
  19. dongle --NFC
  20. LInux中ThreadInfo中的preempt_count字段

热门文章

  1. cocosStudio中使用PageView,ListView和ScrollView
  2. Django-extra的用法
  3. 五、WEB框架基础(1)
  4. 网络摄像机IPCamera RTSP直播播放网络/权限/音视频数据/花屏问题检测与分析助手EasyRTSPClient
  5. Geoffrey E. Hinton
  6. ajax json html 结合
  7. mongodb学习之:文档操作
  8. System.IO.File类和System.IO.FileInfo类
  9. SAP 系统账期开关
  10. matlab面向对象设计---类的概念和使用