#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 6010
#define max(a,b) ( (a)> (b)? (a): (b) )
struct Tree
{
int parent, child, brother;
Tree(){ parent= child= brother= 0; }
}T[MAXN];
int n, ans[MAXN][2];
void dfs( int u ){
int child;
child= T[u].child;
while( child ){
dfs( child );
ans[u][1]+= ans[child][0];
ans[u][0]+= max( ans[child][0], ans[child][1] );
child= T[child].brother; }
}
int main()
{
while( scanf("%d",&n )!= EOF ){
memset( ans, 0, sizeof(ans) );
for( int i= 1; i<= n; ++i ) scanf("%d", &ans[i][1] );
int u, v;
while( scanf("%d%d",&u,&v)!= EOF ){
if( u== 0 && v== 0 ) break;
T[u].parent= v;
T[u].brother= T[v].child;
T[v].child= u;
}
for( int i= 1; i<= n; ++i )
if( T[i].parent== 0 ){
dfs( i );
printf("%d\n", max( ans[i][0], ans[i][1] ) );
break; }
for( int i= 1; i<= n; ++i ){
T[i].parent= 0;
T[i].child = 0;
T[i].brother= 0; }
}
return 0;
}
posted on 2009-05-22 00:19
Darren 閱讀(188)
評(píng)論(0) 編輯 收藏 引用