https://vjudge.net/problem/POJ-2342
题意：在一个公司中，每个职员有一个快乐值ai，现在要开一个party，邀请了一个员工就不可能邀请其直属上司，同理邀请了一个人就不可以邀请其的直属员工，问如何使得这个快乐值达到最大。
思路：dp[maxn][2];
dp[i][0],表示不去,dp[i][1]表示去.设u为i的孩子;
dp[i][0]=(i的全部员工的max(dp[u][1],dp[u][0)相加，也就是其子员工来或不来的最大快乐值。
dp[i][1]=(i的全部员工的dp[u][0相加，也就是其子员工都不能不来的最大快乐值。
从root开始dp，最终结果就是max(dp[root][0],dp[root][1])。
注意：此处已确保关系为一棵树,并且root为根.
类似题目：https://blog.csdn.net/qq_38924883/article/details/82989140
#include<iostream>
#define maxn 6005
using namespace std;
int dp[maxn][2],father[maxn],vis[maxn];
int n;
void dfs(int node)
{for(int i=1;i<=n;i++){if(father[i]==node&&!vis[i]){dfs(i);dp[node][0]+=max(dp[i][0],dp[i][1]);dp[node][1]+=dp[i][0];}}
}
int main()
{ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++)cin>>dp[i][1],vis[i]=0;int x,y,root;while(cin>>x>>y){if(x==0&&y==0) break;father[x]=y;root=y;}dfs(y);cout<<max(dp[root][0],dp[root][1])<<endl;return 0;
}