自动搬运

查看原文

来自洛谷，原作者为

	xler0915 AFO | 可能 PhOer

搬运于2025-08-24 22:40:49，当前版本为作者最后更新于2023-04-20 17:33:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

题意

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

思路：树形 dp

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

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

最终答案即为 $\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;
}