题意：在一个大学庆典中，从n个职工中选择一些人来参加派对，这n个人上司与下属关系形成一颗树，每个人都有一个对应的funny值，为了使派对更加有趣，要求上司与其直接下属不能同时参加派对，并使派对的funny值最大.
还以为是图，问题想复杂了
#include<cstdio> #include<cstring> #include<vector> #define Max(a,b) a>b?a:b using namespace std; const int maxn = 6010; vector<int> g[maxn]; int fa[maxn],vis[maxn]; int dp[maxn][2]; int n; void tree_dp(int u) { vis[u]=1; for(int i=0;i<g[u].size();i++) { int v = g[u][i]; if(!vis[v]) { tree_dp(v); dp[u][0]+=Max(dp[v][0],dp[v][1]); dp[u][1]+=dp[v][0]; } } } int main() { int a,b; while(scanf("%d",&n)!=EOF) { memset(dp,0,sizeof(dp)); memset(fa,0,sizeof(fa)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { scanf("%d",&dp[i][1]); g[i].clear(); } int root,ans; while(scanf("%d%d",&a,&b)&&(a!=0||b!=0)) { fa[a]=b; g[b].push_back(a); root=b; } while(fa[root])root=fa[root]; tree_dp(root); ans=Max(dp[root][0],dp[root][1]); printf("%d\n",ans); } }