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

ID: 101

Type: Default

1000ms

256MiB

Difficulty: 6

Uploaded By:

Tags>

蚂蚁

思路

解法1:树形dp

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

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