Problem-unruled-record

CF212E IT Restaurants

标签：01 背包，dfs

题意

给定一个 $n$，表示有 $n$ 个节点（$1\sim n$）以及接下来 $n-1$ 条边的树，现用两种颜色（红，蓝）对这颗树的节点染色，染色规则是，每个节点有三种状态，要么染成红色，要么染成蓝色，要么不染色，并且规定用一条边连接的两个节点要么染成颜色相同，要么一个染色一个不染色。

问在保证染色节点最多的条件下，红色与蓝色的个数的情况。（要求是至少有一个节点被染成红色，至少一个节点被染成蓝色）。

解法

结论容易看出来，只可能有一个无色格子，剩下两部分要么是红色要么是蓝色。

对于每个节点把每个子树的大小记录下来，然后对这些数进行 01 背包，来计算这些数的组合有哪些，再把答案数组对当前记录哪些数能取到的数组进行每位与。

AC 记录