洛谷P1352-沒有上司的舞會（樹形DP）

題目連結：https://www.luogu.com.cn/problem/P1352

部落格園食用連結：https://www.cnblogs.com/lonely-wind-/p/13488159.html

題目描述

某大學有 n 個職員，編号為 1 … n 1\ldots n 1…n。

他們之間有從屬關系，也就是說他們的關系就像一棵以校長為根的樹，父結點就是子結點的直接上司。

現在有個周年慶宴會，宴會每邀請來一個職員都會增加一定的快樂指數 r i r_i ri​，但是呢，如果某個職員的直接上司來參加舞會了，那麼這個職員就無論如何也不肯來參加舞會了。

是以，請你程式設計計算，邀請哪些職員可以使快樂指數最大，求最大的快樂指數。

輸入格式

輸入的第一行是一個整數 n。

第 2 到第 ( n + 1 ) (n + 1) (n+1)行，每行一個整數，第 ( i + 1 ) (i+1) (i+1) 行的整數表示 i i i 号職員的快樂指數 r i r_i ri​ .第 ( n + 2 ) (n + 2) (n+2)到第 2 n 2n 2n 行，每行輸入一對整數 l , k l, k l,k，代表 k 是 l 的直接上司。

輸出格式

輸出一行一個整數代表最大的快樂指數。

輸入

7

1

1

1

1

1

1

1

1 3

2 3

6 4

7 4

4 5

3 5

輸出

5

說明/提示

資料規模與約定

對于 100 % 100\% 100% 的資料，保證 1 ≤ n ≤ 6 × 1 0 3 1\leq n \leq 6 \times 10^3 1≤n≤6×103， − 128 ≤ r i ≤ 1 ≤ l , k ≤ n -128 \leq r_i\leq1 \leq l, k \leq n −128≤ri​≤1≤l,k≤n，且給出的關系一定是一棵樹。

emmm，蒟蒻發現自己的DP太辣雞了。。。是以來練練DP，這題的話實際上應該算是樹DP的入門題吧，轉移還是挺好想的。

每次在每個節點都會有個選擇，就是選還是不選，如果選的話，那麼它的兒子節點就不能選，如果不選的話它的兒子節點就可以選，也就是說我們需要另開一維狀态來記錄每個節點是否選自己的情況，那麼就很容易得出如下方程：

dp[x][0]+=max(0,max(dp[v][1],dp[v][0]));//如果不選目前節點，那麼兒子節點可以任意選
dp[x][1]+=max(0,dp[v][0]);//如果選擇目前節點，那麼隻能選擇兒子節點不存在的情況
           

以下是AC代碼：

#include <bits/stdc++.h>
using namespace std;

const int mac=1e4+10;

int a[mac],dp[mac][3],father[mac];
vector<int>g[mac];

void dfs(int x,int fa)
{
    dp[x][1]=a[x];
    for (auto v:g[x]){
        dfs(v,x);
        dp[x][0]+=max(0,max(dp[v][1],dp[v][0]));
        dp[x][1]+=max(0,dp[v][0]);
    }
}

int main(int argc, char const *argv[])
{
    int n; 
    scanf ("%d",&n);
    for (int i=1; i<=n; i++) scanf ("%d",&a[i]);
    for (int i=1; i<n; i++){
        int u,v;
        scanf ("%d%d",&u,&v);
        g[v].push_back(u);
        father[u]=v;
    }
    int root=0;
    for (int i=1; i<=n; i++) 
        if (!father[i]) {root=i; break;}
    dfs(root,0);
    printf("%d\n",max(dp[root][1],dp[root][0]));
    return 0;
}