大意：很多领导，能形成一个树形关系网，这些领导参加一个party，每个人都有一个能使party活跃的值，但是每个人又不喜欢跟自己的直接领导同时参加party。为使party气氛最好，，求最好气氛值。
思路：
法一：对子树的根按两种决策找到状态方程，然后用刷表法
法二：细化状态，dp[i][0],dp[i][1] 分别表示不选i时的最大集和选了i时的最大集
法二的方法更实用，状态细化后更便于找状态方程
法二代码：
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N = 6666;int n;int a[N];int fa[N];int dp[N][2];void dfs(int u){for(int i=1;i<=n;i++){if(fa[i]!=u) continue;dfs(i);dp[u][1]+=dp[i][0];dp[u][0]+=max(dp[i][1],dp[i][0]);}}int main(){memset(fa,-1,sizeof(fa));scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int u,v;while(scanf("%d%d",&u,&v)&&(u||v)){fa[u]=v;}for(int i=1;i<=n;i++) dp[i][1]=a[i];for(int i=1;i<=n;i++)if(fa[i]==-1){dfs(i);printf("%d\n",max(dp[i][0],dp[i][1]));break;}return 0;}
法一代码：
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N = 6666;int n;int a[N];int fa[N];int dp[N];int sum_s[N]; //每个结点儿子的最大独立集和int sum_gs[N]; //每个结点孙子的最大独立集和void dfs(int u){for(int i=1;i<=n;i++){if(fa[i]!=u) continue;dfs(i);}dp[u]=max(sum_s[u],sum_gs[u]+a[u]);int f=fa[u];if(f!=-1) sum_s[f]+=dp[u];if(fa[f]!=-1) sum_gs[fa[f]]+=dp[u];}int main(){memset(fa,-1,sizeof(fa));scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int u,v;while(scanf("%d%d",&u,&v)&&(u||v)){fa[u]=v;}for(int i=1;i<=n;i++)if(fa[i]==-1){dfs(i);printf("%d\n",dp[i]);break;}return 0;}
平平淡淡才是真
