「Luogu P1352」没有上司的舞会

Description

给定一棵 $n\ (1 \leq n \leq 6 \times 10^3)$ 个点的树，点 $i\ (1 \leq i \leq n)$ 的点权为 $r_i\ (-128 \leq r_i \leq 127)$ 。现在需要从中选取若干个点，使这些点的点权和最大，但规定子节点和父节点不能同时选，求最大点权和。

Source

[Luogu]P1352

Solution

考虑 树形DP 。

状态：

用 $f_{0,u}$ 表示在节点 $u$ 的子树中，不取 $u$ 的最大点权和；

用 $f_{1,u}$ 表示在节点 $u$ 的子树中，取了 $u$ 的最大点权和。

初始：

无

转移：

$$\large{ f_{0,u} = \sum\limits_{v \in son_u} \max \left( f_{0,v}, f_{1,v}\right) }$$

当不取节点 $u$ 时，$u$ 的子节点取和不取都可以，显然取其中较大的更优，所以 $f_{0,u}$ 应当等于 所有子节点 取 与 不取 的 较大值 之和。

$$\large{ f_{1,u} = r_u + \sum\limits_{v \in son_u} f_{0,v} }$$

当取节点 $u$ 时，$f_{1,u}$ 的最小值为 节点 $u$ 的点权，同时 $u$ 的子节点只能不取，所以 $f_{1,u}$ 还应当加上 所有子节点不取 的和。

答案：

$$\large{\begin{aligned} &\max \left(f_{0,root},f_{1,root} \right) && (root\ 表示根节点) \end{aligned}}$$

答案是在根节点的子树中，取 和 不取 根节点的较大值。

时间复杂度为 $O(n)$ 。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 6000;
int n, l, k, tot, root, r[MAXN + 5], cnt[MAXN + 5], head[MAXN + 5], f[2][MAXN + 5];
struct Edge {
    int next, to;
} e[(MAXN << 1) + 5];

inline void addEdge(int u, int v) {
    e[++tot] = (Edge) { head[u], v };
    head[u] = tot;
}

void dfs(int u) {
    f[1][u] = r[u];
    for (int v, i = head[u]; v = e[i].to, i; i = e[i].next) {
        dfs(v);
        f[0][u] += max(f[0][v], f[1][v]);
        f[1][u] += f[0][v];
    }//转移 
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(r[i]);
    for (int i = 1; i < n; ++i) {
        read(l), read(k);//k 是 l 的上司 
        addEdge(k, l);//连一条有向边 k -> l
        ++cnt[l];//l 的上司数量 
    }
    for (int i = 1; i <= n; ++i)
        if (!cnt[i]) {
            root = i;
            break;
        }//找根节点（没有父亲的节点） 
    dfs(root);
    write(max(f[0][root], f[1][root]));//答案
    putchar('\n');
    return 0;
}