题目链接：

题目大意：在一个公司中，每个职员有一个快乐值ai，现在要开一个party，邀请了一个员工就不可能邀请其直属上司，同理邀请了一个人就不可以邀请其的直属员工，

问如何使得这个快乐值达到最大。

题解：对每个结点dp[i][0]表示不邀请这个员工，其子树达到的最大快乐值，dp[i][1]表示邀请i员工其子树达到的最大值。

dp[i][0]=(i的全部员工的max(dp[u][1],dp[u][0)相加，也就是其子员工来或不来的最大快乐值。

dp[i][1]=(i的全部员工的dp[u][0相加，也就是其子员工都不能不来的最大快乐值。

从大boss开始dp，最终结果就是max(dp[root][0],dp[root][1])

代码：

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn = 6060;int n, happy[maxn], dp[maxn][2], p[maxn];vector
       
         sons[maxn];bool vis[maxn];void dfs(int u) {    if (vis[u]) return;    vis[u] = true;    dp[u][1] = happy[u], dp[u][0] = 0;    for (int i = 0; i < sons[u].size(); i ++) {        int v = sons[u][i];        if (v == p[u]) continue;        dfs(v);        dp[u][1] += dp[v][0];        dp[u][0] += max(dp[v][1], dp[v][0]);    }}void test() {    for (int i = 1; i <= n; i ++) {        cout << "dp[" << i << "] = " << dp[i][1] << " , " << dp[i][0] << endl;    }}int main() {    while (cin >> n) {        if (!n) break;        fill(p+1, p+1+n, -1);        fill(vis+1, vis+1+n, false);        for (int i = 1; i <= n; i ++) cin >> happy[i];        int a, b;        for (int i = 1; i < n; i ++) {            cin >> a >> b;            p[a] = b;            sons[b].push_back(a);        }        int root = 1;        while (p[root] != -1) root = p[root];        dfs(root);        cout << max(dp[root][1] , dp[root][0]) << endl;        // test();    }    return 0;}
       
      
     
    

参考链接：