标签：ch int MAX 子树 树形 动态 规划 节点 dp

一、问题简述

有一棵 \(n\) 个节点组成的树，每个节点 \(a_i\) 有一个权值 \(a_i.worth\)。求子树的点权值和的最大值。

---

二、算法简析

该问题要用树形dp求解。
设 \(dp[u] =\) 以 \(u\) 为根节点的子树的点权值和的最大值。我们采用邻接表的形式存储边，\(G[u] =\) 以 \(u\) 为起点的边的集合，则 \(v\in \{G[u][i]~|~0\leq i \leq G[u].size() \}\) 为 \(u\) 的孩子。
以 \(u\) 为根节点的子树肯定有 \(u\)，所以 \(dp[u]\) 的初始值为 \(u.worth\)。以 \(u\) 的孩子 \(v\) 为根节点的子树，是否要加入以 \(u\) 为根节点的子树，取决于 \(dp[v]\) 是否大于 \(0\)。只要 \(dp[v]>0,~v\in \{G[u][i]~|~0\leq i < G[u].size() \}\)，就要 \(dp[u]~\text{+=}~dp[v]\)。
所以，方程为：

\[\begin{split} dp[u] = u.worth + \sum_{v\in G[u]} \text{max}(dp[v], 0) \\ \end{split} \]

最后，我们只要遍历 \(dp[]\)，找到最大值即可。

---

三、相关题目

3.1 P8625 [蓝桥杯 2015 省 B]

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 3;

typedef long long ll;

int A[MAX], n;
vector<int> G[MAX];
ll dp[MAX];
bool vis[MAX];

int quickin(void)
{
	int ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

void dfs(int u, int pre)
{	
	dp[u] = A[u];
	for (int i = 0; i < G[u].size(); i++)
	{
		int v = G[u][i];
		if (v != pre)
		{
			dfs(v, u);
			if (dp[v] > 0)
				dp[u] += dp[v];
		}
	}
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	n = quickin();
	for (int i = 1; i <= n; i++)
		A[i] = quickin();
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		a = quickin(), b = quickin();
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	dfs(1, 0);
	
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		ans = max(ans, dp[i]); 
	
	cout << ans << endl;
	
	return 0;	
} 

注：

• 1、该问题允许空集存在，所以 \(ans \geq 0\)，即 \(ans\) 的初始值为 \(0\)。

3.2 P1122 最大子树和

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 3;

typedef long long ll;

int A[MAX], n;
vector<int> G[MAX];
ll dp[MAX];
bool vis[MAX];

int quickin(void)
{
	int ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

void dfs(int u, int pre)
{	
	dp[u] = A[u];
	for (int i = 0; i < G[u].size(); i++)
	{
		int v = G[u][i];
		if (v != pre)
		{
			dfs(v, u);
			if (dp[v] > 0)
				dp[u] += dp[v];
		}
	}
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	n = quickin();
	for (int i = 1; i <= n; i++)
		A[i] = quickin();
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		a = quickin(), b = quickin();
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	dfs(1, 0);
	
	ll ans = dp[1];
	for (int i = 1; i <= n; i++)
		ans = max(ans, dp[i]); 
	
	cout << ans << endl;
	
	return 0;	
} 

注：

• 1、与上题不同，该题不允许出现空集，所以 \(ans\) 即 \(dp[]\) 中的最大值，不需要与 \(0\) 比较，可能为负值。

---

完

标签：ch,int,MAX,子树,树形,动态,规划,节点,dp
From： https://www.cnblogs.com/hoyd/p/18032405