「Luogu P1122」最大子树和

Description

给定一棵 $n\ (1 \leq n \leq 16000)$ 个点的树，节点 $i$ 的点权为 $val_i\ \left( \left | \sum\limits_{i=1}^n val_i \right | \leq 2^{31}-1 \right)$，现在要从中找到一个联通分量，使它们的点权和最大， 求这个最大值。

Source

[Luogu]P1122

Solution

看到这种求最大值的题目，很容易想到 树形DP 。

状态：

用 $f_u$ 表示在节点 $u$ 的子树中，包括 $u$ 的联通分量的最大点权和。

初始：

$$\large { f_u = val_u }$$

由状态可知，$f_u$ 一定取了节点 $u$，所以最小值为 $val_u$ 。

转移：

$$\large { f_u = \max \left( f_u, f_u + f_v \right) }$$

如果加上包括子节点 $v$ 的联通分量后，比原来的值大，显然加上更优。

答案：

$$\large {\begin{aligned} & \max \begin{Bmatrix} f_u \end{Bmatrix} & \left( 1 \leq u \leq n \right) \end{aligned}}$$

不能判断 $f_{root}$（$root$ 表示根节点）就是答案，因为最优答案不一定取根节点，可能取其它节点（不选根节点）的方案更优，所以要取最大值。

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 = 16000, MAXM = 16000;
int n, tot, ans, val[MAXN + 5], head[MAXN + 5], f[MAXN + 5];
struct Edge {
    int next, to;
} e[(MAXM << 1) + 5];

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

void dfs(int u, int fa) {
    f[u] = val[u];//初始 
    for (int v, i = head[u]; v = e[i].to, i; i = e[i].next) {
        if (v == fa) continue;
        dfs(v, u);
        f[u] = max(f[u], f[u] + f[v]);//转移 
    }
    ans = max(ans, f[u]);//取最大值 
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(val[i]);
    for (int i = 1; i < n; ++i) {
        int u, v;
        read(u), read(v);
        addEdge(u, v), addEdge(v, u);//无向边 
    }
    dfs(1, 0);//假设根节点为 1 
    write(ans);
    putchar('\n');
    return 0;
}