2023.03.21-第二题-红白染色树 - Problem Detail - CodeFun2000

1000ms

Difficulty: 6

所属公司 : 蚂蚁

时间 :2023年3月21日

算法与标签>树形DP

会员或题库专享

请先，开通会员或购买题库蚂蚁机考题库，可解锁完整内容。

购买蚂蚁机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（蚂蚁机考题库），可解锁完整内容。

购买题库开通会员

思路

解法1:树形dp

树上dp. $dp_{i,j}$ 代表以 $i$ 为根，且 $color(i)$ 是 $red/white$ 下的最优解。转移为:

\large dp_{i,j} = \sum_{s 是 i 的儿子} dp_{s,j \oplus 1}