思路与证明

• 按位分治

  • 将答案拆成每一位的贡献之和：对于每个比特位 $b \in [0,,29]$，独立求可置为 $1$ 的节点个数，贡献为该个数乘以 $2^b$。

• 对固定一位 $b$ 的约束

  • 若某条边该位为 $1$（即该边属于“$1$-边”），则两端点该位都必须为 $1$。
  • 若某条边该位为 $0$（即该边属于“$0$-边”），则两端不能同时为 $1$，等价于独立集限制。

• 强制赋值与森林独立集

题目内容

给定一棵包含 $n$ 个节点的无向树，节点编号为 $1$ ~ $n$ 。每条边 $(u,v)$ 给定一个权值 $w_{u,v}$ ，代表满足下面的按位与约束：

$a_u$ & $a_v= w_{u,v}$ 。其中 $a_i$ 为需要分配给节点 $i$ 的非负整数，且满足 $a_i<2^{30}$ 。

请在满足所有边的按位与约束的前提下，最大化所有节点值之和 $\sum^n_{i=1}a_i$ ，并输出该最大值；数据保证答案存在。

【名词解释】