[Kickstart Round F 2019 C. Spectating Villages] 树形DP

1. 题目链接

Kickstart Round F 2019 C. Spectating Villages

2. 题目描述

有 $V$ $(2\le N\le 10^5)$ 个村庄，他们由 $V-1$ 条无向边直接或间接相连，无重边，无自环。每个村庄有一个漂亮值(即点权)，编号为 $i$ 的村庄的漂亮值为 $B_i$ $(-10^5\le B_i \le 10^5)$。
你可以选择在一些村庄安装电灯，如果你在一个村庄安装了电灯，那么这个村庄以及与这个村庄直接相连的所有村庄也将被点亮。
现在你可以在一些村庄上安装电灯（也可以都不安装），求被点亮的村庄的漂亮值之和的最大值。

3. 解题思路

图是一个棵无根树。可以选择某一个顶点作为根节点进行树形DP。
状态定义为 ：

• $dp[u][0]$ 表示村庄 $u$ 为根节点的子树中，在村庄 $u$ 没有安装电灯，同时村庄 $u$ 不被点亮的条件下的最大漂亮值之和。
• $dp[u][1]$ 表示村庄 $u$ 为根节点的子树中，在村庄 $u$ 安装了电灯的条件下的最大漂亮值之和。
• $dp[u][2]$ 表示村庄 $u$ 为根节点的子树中，在村庄 $u$ 没有安装电灯，同时村庄 $u$ 被点亮的条件下的最大漂亮值之和。

对于村庄 $u$ 为根节点的子树中，有：

• 当村庄 $u$ 没有安装电灯，同时村庄 $u$ 不被点亮：其子节点一定不能安装电灯。
• 当村庄 $u$ 安装了电灯：其子节点可以随意。
• 当村庄 $u$ 没有安装电灯，同时村庄 $u$ 被点亮：他的子节点中至少有一个安装了电灯。我们这里可以选$\arg\max_\limits{v \in son(u)}\lbrace dp[v][1]-\max\lbrace dp[u][0],dp[u][1]\rbrace\rbrace$ 被点亮，其他子节点可以随意。

具体的转移方程可以见代码。

4. 参考代码

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

typedef long long ll;
typedef unsigned long long ull;

const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

template<typename T> void umax(T& a, const T b) { a = max(a, b); }
template<typename T> void umin(T& a, const T b) { a = min(a, b); }

const int MAXN = 1e5 + 5;
int T, N;
ll B[MAXN];
vector<int> edge[MAXN];
ll ans, dp[MAXN][3];

ll dfs(int u, int fa) {
    dp[u][0] = 0, dp[u][1] = B[u]; 
    ll mv = -1, mx = -infl;
    // choose one of child v with max{dp[v][1]-max{dp[v][0], dp[v][2]}}
    for(auto& v : edge[u]) {
        if(v == fa) continue;
        dfs(v, u);
        ll buxuan = max(dp[v][0], dp[v][2]);
        if(mx < dp[v][1] - buxuan) {
            mx = dp[v][1] - buxuan;
            mv = v;
        }
    }
    if(mv == -1) dp[u][2] = -infl;
    else dp[u][2] = B[u];
    for(auto& v : edge[u]) {
        if(v == fa) continue;
        ll buxuan = max(dp[v][0], dp[v][2]);
      	// not chosen and not illuminated
        dp[u][0] += max(dp[v][0], dp[v][2]);
      	// chosen and illuminated
        dp[u][1] += max(dp[v][1], max(dp[v][0] + B[v], dp[v][2]));
      	// not chosen and illuminated
        if(mv == v) dp[u][2] += dp[v][1];
        else dp[u][2] += max(buxuan, dp[v][1]);
    }
    ll ret = 0;
    umax(ret, dp[u][0]);
    umax(ret, dp[u][1]);
    umax(ret, dp[u][2]);
    return ret;
}

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-3.txt", "r", stdin);
#endif
    scanf("%d", &T);
    for(int cas = 1; cas <= T; ++cas) {
        scanf("%d", &N);
        for(int i = 1; i <= N; ++i) {
            scanf("%lld", &B[i]);
            edge[i].clear();
        }
        for(int i = 1; i <= N - 1; ++i) {
            int u, v; scanf("%d %d", &u, &v);
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        ll ans = 0;
        umax(ans, dfs(1, 1));
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}