题目内容

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

定义操作A：

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

思路：树形DP

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

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

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