#include
<
iostream
>
using
namespace
std;
int
N;
int
root;
int
val[
6010
];
int
chd[
6010
],now[
6010
],pre[
6010
],f0[
6010
],f1[
6010
];
inline
int
max(
int
x,
int
y){
return
x
>
y
?
x:y;
}
void
treedp(
int
x){
f1[x]
=
val[x]; f0[x]
=
0
;
while
(now[x]){
treedp(chd[now[x]]);
f1[x]
+=
f0[chd[now[x]]];
f0[x]
+=
max(f1[chd[now[x]]],f0[chd[now[x]]]);
now[x]
=
pre[now[x]];
}
}
int
main()
{
scanf(
"
%d
"
,
&
N);
for
(
int
i
=
1
;i
<=
N;
++
i)
scanf(
"
%d
"
,
&
val[i]);
int
x,y;
memset(now,
0
,
sizeof
(now));
root
=
N
*
(N
+
1
)
/
2
;
for
(
int
i
=
1
;i
<
N;
++
i){
scanf(
"
%d%d
"
,
&
x,
&
y);
chd[i]
=
x;
pre[i]
=
now[y];
now[y]
=
i;
root
-=
x;
}
scanf(
"
%d%d
"
,
&
x,
&
y);
treedp(root);
printf(
"
%d\n
"
,max(f0[root],f1[root]));
return
0
;
}
posted on 2009-05-30 10:35
xfstart07 阅读(180)
评论(0) 编辑 收藏 引用 所属分类:
代码库