poj 2342(树形DP)

poj 2342
树形DP基础题，具体看注释。
设状态$f[i][0]$为$i$不来，$f[i][1]$为$i$要来
$f[r][1] += f[i][0]$ r要来，i为r的下属
$f[r][0] += max(f[i][0], f[i][1])$ /不来，i为r的下属

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define ms(i,j) memset(i, j, sizeof(i));
using namespace std;
const int maxn = 6005;
int f[maxn][2];
bool visit[maxn];
int father[maxn];
int n;
void dfs(int r)
{
    visit[r] = true;
    for (int i=1;i<=n;i++)
    {
        if (!visit[i]&&father[i]==r)//没有访问过的点并且i是r的下属
        {
            dfs(i);//向叶子结点DFS，在叶子节点DP
            f[r][1] +=  f[i][0];
            f[r][0] +=  max(f[i][0], f[i][1]);
        } 
    }
}
int main()
{
    while (scanf("%d", &n)==1)
    {
        ms(f,0);
        ms(visit, false);
        ms(father, 0);
        for (int i=1;i<=n;i++) scanf("%d", &f[i][1]);
        int root = 0;//找最大权利的监督者(树根) 
        int l,k;
        while (scanf("%d%d", &l, &k)==2&&(l||k))
        {
            father[l] = k;//k监督l 
            if (root==l)
            {
                root = k;
            }
        }
        dfs(root);
        printf("%d\n", max(f[root][0], f[root][1]));
    }
    return 0;
}