题目描述：
一棵二叉树，存在点权。不能同时取一条边的两个点，返回二叉树能得到的最大权值。
数据范围：
$1\le n \le 10^4;0\le val \le 10^4$
题解：
很明显需要使用树形dp，每个节点需要记录两个值，该子树取该节点能得到最大权值，该子树不取该节点能得到的最大权值，使用 $dp[node][1/0]$ 表示。
需要注意的是， $dp[root][0]$ 的值，不能只用子节点的 $1$ 值更新。因为子树的最大权值为 $max(dp[root][0], dp[root][1])$ .
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
unordered_map<TreeNode *, int[2]> dp = {};
void dfs(TreeNode *root)
{
if (root == nullptr)
return;
dfs(root->left);
dfs(root->right);
dp[root][0] = max(dp[root->left][0], dp[root->left][1]) + max(dp[root->right][0], dp[root->right][1]);
dp[root][1] = dp[root->left][0] + dp[root->right][0] + root->val;
}
int rob(TreeNode *root)
{
dfs(root);
return max(dp[root][0], dp[root][1]);
}
};
|