ARC083C Bichrome Tree

题意：给出一棵 个点的有根树，点 有参数 。

点可以染成黑白两色之一，且可以赋予一个自然数权值。

需要使得每个点 的子树内（包括 本身）与 同色的点权和恰为 。

判定是否存在一组符合要求的染色方案。

，，时限 。

---

先考虑最稳健的布尔 。

记 表示 子树内与 同色点权和为 ，异色点权和为 的方案是否存在。

转移时，记 表示同色权值和为 ，异色权值和为 。

对于直接儿子 ， 可以贡献 或者 。

在每个儿子处选一个二元组，然后加起来，记为 。

最后 本身可以贡献任意的 。故 需要满足 即可贡献。

由于合法约束形如 ，可以得到贪心策略：

对于同一颗子树，若 ，且 ，则选择 。因为前者贡献的两个对子严格优于（更可能合法）后者贡献的两个。

于是，可以将状态改为： 表示 子树内与 同色的点权和为 ，异色点权和的最小值。

现在问题相当于：给出若干个对子，可以选择翻转其中的一些，需要使得左侧权值和 ，右侧权值和尽量小。

注意到两侧的和是固定的，故只需左侧的和尽量大。跑 01 背包即可。

利用 std::bitset，复杂度可以做到 。