// 题意： 每个节点有权值，子节点和父节点不能同时选，问最后能选的最大价值是多少？
// 那么每个点就有两种选择 选或不选了
//第一道树形DP，虽然1Y了、不过好慢
//HDu上这题居然是多组数据、然后我就超时了、表示还要好好研究
//我感觉我不怎么会建树、、
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #include <vector> #define N 6002 using namespace std; vector <int > v[N]; bool b[N]; int dp[N][2],hp[N]; void dfs(int k) { int i,len=v[k].size(); dp[k][0]=0; dp[k][1]=hp[k]; if(len==0) return ; for(i=0;i<len;i++) dfs(v[k][i]); for(i=0;i<len;i++) { dp[k][0]+=dp[v[k][i]][1]>dp[v[k][i]][0]?dp[v[k][i]][1]:dp[v[k][i]][0]; dp[k][1]+=dp[v[k][i]][0]; } } int main() { int i,n; int k,l; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&hp[i]),b[i]=0; while(scanf("%d %d",&l,&k),k||l) { v[k].push_back(l); b[l]=1; } for(i=1;i<=n;i++) if(!b[i]) break; b[i]=1; dfs(i); printf("%d\n",dp[i][0]>dp[i][1]?dp[i][0]:dp[i][1]); } return 0; }
//不明白为什么就这么小小修改下就过了、、和刚刚超时比起来，快了N多、、hdu真是好奇怪呀
//要去学下左孩子右兄弟表示方法
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#define N 6002
using namespace std;
vector <int > v[N];
bool b[N];
int dp[N][2],hp[N];
void dfs(int k)
{
int i,len=v[k].size();
dp[k][0]=0;
dp[k][1]=hp[k];
if(len==0)
return ;
for(i=0;i<len;i++)
{
dfs(v[k][i]);
dp[k][0]+=max(dp[v[k][i]][1],dp[v[k][i]][0]);
dp[k][1]+=dp[v[k][i]][0];
}
}
int main()
{
int i,n;
int k,l;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&hp[i]),v[i].clear();
memset(b,0,sizeof(b));
while(scanf("%d%d",&l,&k),k||l)
{
v[k].push_back(l);
b[l]=1;
}
for(i=1;i<=n;i++)
if(!b[i])
break;
b[i]=1;
dfs(i);
printf("%d\n",dp[i][0]>dp[i][1]?dp[i][0]:dp[i][1]);
}
return 0;
}