自动搬运

查看原文

来自洛谷，原作者为

	lym2022 这个人很勤快，但不想留下什么

搬运于2025-08-24 21:18:16，当前版本为作者最后更新于2025-04-22 16:46:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

树形 dp 的板子题。

双倍经验

题目大意

给定一棵树的每条边和每个点的点权，规定如果点 $u$ 选了，那么点 $u$ 的儿子 $v$ 就不能选,问可以选出的方案中点权和最大是多少。当 $u$ 为 $0$ 时，点 $v$ 为根节点。

思路

典型的树形 dp。

$f[u][0]$ 表示以 $u$ 为根节点的子树，节点 $u$ 不选时的最大值，初始化时因为没人来，所以 $f[u][0]$ 初始化为 $0$；

$f[u][1]$ 表示以 $u$ 为根节点的子树，节点 $u$ 选时的最大值，初始化时因为只有 $u$ 一个节点，所以 $f[u][0]$ 初始化为 $u$ 的点权；

转移时从下向上转移：

当 $u$ 不选时儿子 $v$ 可选可不选，所以 $f[u][0]$ 就加上 $f[v][0]$ 和 $f[v][1]$ 较大的那个（不写函数是因为不会用格式）;

当 $u$ 选时儿子 $v$ 就不能选，所以 $f[u][1]$ 就加上 $f[v][0]$。

最后就输出根节点选或不选的最大值就好了。

Code

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

const int N = 1e5 + 5;

int n,a[N],f[N][2],root;     //a数组就是点权，root存根节点 

vector<int> e[N];

void dfs(int u) {                        //树形dp 
	f[u][0] = 0;                         //不选时，初始化为 0 
	f[u][1] = a[u];                      //选时，初始化为 u 的点权 
	for(auto v : e[u]) {                 //便利每个儿子 v 
		dfs(v);                          //先搜下去，等到儿子的答案确定了再转移 
		f[u][1] += f[v][0];              //如果 u 选，v 就不能选 
		f[u][0] += max(f[v][0],f[v][1]); //否则 v 就可选可不选 
	} 
}

int main() {
	cin >> n;
	for(int i = 1;i<=n;i++) {
		int u,v,w;
		cin >> u >> v >> w;
		a[v] = w;
		if(u == 0) {          //如果 u 为 0,那么 v 就是根节点  
			root = v;         //记录根节点 
			continue;
		}
		e[u].push_back(v);    //邻接表存图 
	}
	dfs(root);           //从根节点开始搜 
	cout << max(f[root][0],f[root][1]);     //输出根节点选或不选时答案较大的情况 
	return 0;
}

有兴趣的话可以浏览一下蒟蒻写的前两篇题解：

P1032 子串变换 P10687 True Liars