推薦題解
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=6000+10;
int n;
vector<int>e[maxn];
int a[maxn];
int dp[maxn][2];
bool have[maxn];
struct _rank
{
int r;
int num;
}ran[maxn];
bool tem(_rank a,_rank b)
{
return a.r>b.r;
}
void work(int x)
{
for(int i=0;i<e[x].size();i++)
{
ran[e[x][i]].r=ran[x].r+1;
work(e[x][i]);
}
}
int main()
{
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
memset(have,false,sizeof(have));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
ran[i].num=i;
ran[i].r=0;
e[i].clear();
}
while(1)
{
int l,k;
scanf("%d%d",&l,&k);
if(!l&&!k) break;
e[k].push_back(l);
have[l]=true;
}
for(int i=1;i<=n;i++)
{
if(have[i]==false)
work(i);
}
sort(ran+1,ran+n+1,tem);//對等級進行排序
for(int i=1;i<=n;i++)//ran[i].num為根
{
dp[ran[i].num][1]+=a[ran[i].num];
for(int j=0;j<e[ran[i].num].size();j++) //e[ran[i].num][j]為葉子
{
dp[ran[i].num][1]+=dp[e[ran[i].num][j]][0];
dp[ran[i].num][0]+=max(dp[e[ran[i].num][j]][0],dp[e[ran[i].num][j]][1]);
}
}
int ans=0;
for(int j=n;j>=1;j--)
if(ran[j].r==0) ans+=max(dp[ran[j].num][1],dp[ran[j].num][0]);
printf("%d\n",ans);
}
return 0;
}