思路与证明

• 按位分治

  • 将答案拆成每一位的贡献之和：对于每个比特位 $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$ ，并输出该最大值；数据保证答案存在。

【名词解释】

【按位与运算】按位与运算指对两个整数的二进制表示进行逻辑与操作，只有对应位均为 $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$ 。

输出描述

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

样例1

输入

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$ 。

样例2

输入

4
1 2 3
2 3 1
2 4 0

输出

3221225467