#include <iostream>
#include <cstdio>
#include <cstring>
struct Tree{
int father;
int child;
int brother;
int NOT;
int s;
int Max(){
return s > NOT ? s : NOT;
}
void Init(){
father=child=brother=NOT=0;
}
}tree[60001];
void dfs(int v)
{
int child;
child=tree[v].child;
while(child){
dfs(child);
tree[v].s+=tree[child].NOT;
tree[v].NOT+=tree[child].Max();
child=tree[child].brother;
}
}
int main()
{
int n;
while(~scanf("%d",&n)){
for(int i=1; i<=n; i++){
scanf("%d",&tree[i].s);
tree[i].Init();
}
int f,c;
while(scanf("%d%d",&c,&f)&&f+c){
tree[c].father=f;
tree[c].brother=tree[f].child;
tree[f].child=c;
}
for(int i=1;i<=n;i++){
if(!tree[i].father){
dfs(i);
printf("%d\n",tree[i].Max());
}
}
}
}
分享到:
相关推荐
树型DP和状态压缩DP acm 树型DP和状态压缩DP acm 树型DP和状态压缩DP acm
基本思路 设有一棵以j为根的树,设f[i,j](0,1)表示j点的第i状态的最小值。 状态:0——j点未被监控,在j点放置,控制父结点和子结点。1——j点未被监控,在j点子结点和子结点的子结点放置,保证子结点中至少有一....
树型DP和状态压缩DP+acm.ppt
动态规划算法中的树型DP
很详细的树型DP(选课) 初学者最好的帮助
js做的树型结构,应该是很好的,javascript作的树型结构javascript作的树型结构javascript作的树型结构javascript作的树型结构javascript作的树型结构javascript作的树型结构javascript作的树型结构javascript作的树型...
经典入门 - 树型动态规划和...树本身就是一个递归的结构,所以在树上进行动态规划或者递推是在合适不过的事情。 必要条件:子树之间不可以相互干扰,如果本来是相互干扰的,那么我们必须添加变量使得他们不相互干扰。
树型结构算法树型结构算法树型结构算法树型结构算法
网络拓扑结构大全和图片星型总线型环型树型分布式网状拓扑结构.pdf网络拓扑结构大全和图片星型总线型环型树型分布式网状拓扑结构.pdf网络拓扑结构大全和图片星型总线型环型树型分布式网状拓扑结构.pdf网络拓扑结构...
网络拓扑结构大全和图片星型总线型环型树型分布式网状拓扑结构.doc
分享给大家:基于XML的树型结构编码及结构相似性匹配方法
javascript作的树型结构javascript作的树型结构javascript作的树型结构
树型结构是一类重要的非线性数据结构,而二叉树是最为重要,最为常用的类型。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得到广泛应用,如在编译程序...
delphi7 树型控件 自动根据数据集生成树型结构
pb9 用datawindow 实现 treeview 树型结构
本例是用JSP+EXTJS+JSON+MYQL实现的树型结构,例子结构清晰,便于学习。
简单树型结构 js 用html .可以做任何动态页面(jsp asp php)
我的树型结构练习使用我的树型结构练习使用我的树型结构练习使用我的树型结构练习使用
刚入门级别.C#树型控件的练习使用.
树型论坛树型论坛树型论坛树型论坛树树型论坛型论坛树型论坛