按位分治
- 将答案拆成每一位的贡献之和：对于每个比特位 $b \in [0,,29]$ ，独立求可置为 $1$ 的节点个数，贡献为该个数乘以 $2^b$ 。
对固定一位 $b$ 的约束
- 若某条边该位为 $1$ （即该边属于“ $1$ -边”），则两端点该位都必须为 $1$ 。
- 若某条边该位为 $0$ （即该边属于“ $0$ -边”），则两端不能同时为 $1$ ，等价于独立集限制。

P3407.第2题-无向树节点的最大值

1000ms

Difficulty: 7

所属公司 : 阿里

算法与标签>树形DP

题目内容

给定一棵包含 $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$ ，并输出该最大值；数据保证答案存在。

【名词解释】

【按位与运算】按位与运算指对两个整数的二进制表示进行逻辑与操作，只有对应位均为 $1$ 时该位结果为 $1$ ，否则为 $0$ 。

第一行输入一个整数 $n(1 ≦ n ≦ 2×10^5)$ ，表示节点数。

接下来 $n-1$ 行，每行输入三个整数

$u,v,w (1 ≦ u,v≦n, u≠v,0≦w< 2^{30})$ ，表示在节点 $u,v$ 之间有一条边，且要求 $a_u$ & $a_v = w$ 。

输出一个整数——在满足所有按位与约束的前提下，所有节点值之和的最大可能值：数据保证答案存在。

输入

3
1 2 1
2 3 0

输出

2147483646

说明

解释：

第 $0$ 位：边 $(1,2)$ 要求两端均为 $1$ ，边 $(2,3)$ 要求至少一端为 $0$ ，故最低位赋值为 $[1,1,0]$ ，贡献和 $2$ 。

第 $1$ ~ $29$ 位：所有边对应位均为 $0$ ，等价于求树的最大独立集。都可以选 $1$ 和 $3$ 号点做贡献，贡献和 $2×(2^1+···2^{29})= 2147483644$ 。

输入

输出

3221225467

输入

预期输出（选填）