学步园

看到了一样的题，直接把POJ上的替贴了进来，发现TLE了HDU上的测试数也太多了吧，分析了下POJ的代码，发现时间复杂度过高（有点暴力倾向），只要修改代码了。。。

题意：

某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。

思路：

任何一个点的取舍可以看作一种决策，那么状态就是在某个点取的时候或者不取的时候，以他为根的子树能有的最大活跃总值。分别可以用f[i,1]和f[i,0]表示第i个人来和不来直接记录在结构体中~

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
using namespace std;
#define N 6001
struct node
{
    int father;
    int child;
    int brother;
    int attend;//参加了
    int notattend;//没有参加
    void init()
    {
        father=0;
        child=0;
        brother=0;
        notattend=0;
    }
} p[N];
void dfs(int start)
{
    int child;
    child=p[start].child;
    while(child)
    {
        dfs(child);
        p[start].attend+=p[child].notattend;
        if(p[child].attend>p[child].notattend)
            p[start].notattend+=p[child].attend;
        else
            p[start].notattend+=p[child].notattend;
        child=p[child].brother;//兄弟结点
    }
}
int main()
{
    int n,root;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1; i<=n; i++)
        {
            p[i].init();
            scanf("%d",&p[i].attend);
        }
        int a,b;
        while(scanf("%d%d",&a,&b),a||b)
        {
            root=b;
            p[a].father=b;
            p[a].brother=p[b].child;
            p[b].child=a;
        }
        while(p[root].father)//寻找父节点
            root=p[root].father;
        dfs(root);
        printf("%d\n",p[root].attend>p[root].notattend?p[root].attend:p[root].notattend);
    }
}