hdu1520(树状dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1520

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=6050;
vector<int>son[MAXN];
int f[MAXN];//father 
int v[MAXN];
int dp[MAXN][2];

void dfs(int p)
{
    int len=son[p].size();
    dp[p][1]=v[p];
    for(int i=0;i<len;i++){
        int j=son[p][i];
        dfs(j);
        dp[p][0]+=max(dp[j][1],dp[j][0]);
        dp[p][1]+=dp[j][0];
    }
}

int main()
{
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++)
        {
            cin>>v[i];
            son[i].clear();
            f[i]=-1;
            dp[i][0]=dp[i][1]=0;
        }
        int a,b;
        while(cin>>a>>b)
        {
            if(a==0&&b==0)
                break;
            f[a]=b;
            son[b].push_back(a);
        }

        a=1;
        while(f[a]!=-1)
            a=f[a];//找根节点 
        dfs(a);
        cout<<max(dp[a][1],dp[a][0])<<endl;
    }
    return 0;
}