原题链接
题意：
给一棵树，每个点都有权值a[i]，要求从中选若干个点，满足该点和其父亲节点不能同时被选择，求最大权值。
思路：
一般树形DP的第一维都是子树的编号，我们用dp[i]表示选完以i为根节点的子树能够获得的最大权值。
一个点是否被选择，和他的父节点是否被选择有关，在此基础上再加一维度表示该点是否被选择，即dp[i] [0]表示不选择节点i且选完以i为根节点的子树能够获得的最大权值，dp[i] [1]表示选择节点i且选完以i为根节点的子树能够获得的最大权值。
再来考虑状态转移，因为子节点和父节点不能被同时选择，所以当选择父节点时，就不能再选择直接的子节点，即dp[i][1]=a[i]+max(dp[j][0]) j∈i的子树；当不选择父节点时，是否选择子节点都可以，即dp[i][０]=max(dp[j][0],dp[j][1])，j∈i的子树；
答案即max(dp[root][0],dp[root][1]);
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=6000+100; vector<int>v[maxn]; bool st[maxn];///是否没有上司 int a[maxn];///快乐指数 int n; int dp[maxn][2]; void dfs(int u){ dp[u][1]=a[u]; for(auto t:v[u]){ dfs(t); dp[u][1]+=dp[t][0]; dp[u][0]+=max(dp[t][0],dp[t][1]); } } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<n;i++){ int l,k; cin>>l>>k; ///ｋ是l的直接上司 ｋ指向l st[l]=1; v[k].push_back(l); } int root=1; while(st[root]) root++; dfs(root); cout<<(max(dp[root][0],dp[root][1])); return 0; }
参考：《算法竞赛进阶指南》
