P8625 题解

· · 题解

题目传送门 / 可能有更好的阅读体验

题意

对于一棵树，找到其点权和最大的一个连通分量（注意可以为空），输出这个连通分量的点权和。相似于 P1122。

思路：树形 dp

我们用 a_i 表示第 i 个点的权值，dp_u 表示在以 u 为根的子树中最大的点权和，不妨设 1 号节点为这棵树的根，其父亲为 0 号节点。

因为对于 u 的任意一个儿子 v，如果 dp_v>0，那么以 u 为根的点权和最大的子树一定要加上以 v 为根的点权和最大的子树，所以得到状态转移方程为：

dp_u = a_u+\sum\limits_{u \to v}\max\{dp_v,0\}

最终答案即为 \max\{\max_{i=1}^ndp_i,0\}（因为可以为空），实现方法较为简单。

代码

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

int n;
int a[100005]; // 每个点的点权
long long dp[100005]; // 注意开 long long
vector<int> adj[100005]; // 邻接表存储

void dfs(int u, int fa) {
    dp[u] = a[u];
    for(int v : adj[u]) {
        if(v == fa) continue;
        dfs(v, u);
        dp[u] += max(dp[v], 0ll);
    }
   // 状态转移方程
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        scanf("%d", &a[i]);
    for(int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    printf("%lld", max(*max_element(dp + 1, dp + n + 1), 0ll)); // 输出答案。
    return 0;
}