ID: 459

Difficulty: 8

所属公司 : 美团

时间 :2023年8月12日

题目内容

给定一棵树，每个节点都有一个权值以及最开始是白色。

定义操作A：

选择两个有边直接相连的节点，可以将两个节点同时染红.当且仅当他们都是白色

思路：树形DP

题意类似的题：P1431-塔子哥的树

树形DP 问题。考虑DP的状态定义：

$dp[i][0]$ 表示以 i 为子树，不选择 i 这个节点进行染色，i 这棵子树可以染色的结点最大数量
$dp[i][1]$ 表示以 i 为子树，对 i 这个节点进行染色，i 这棵子树可以染色的结点最大数量