题目内容

给定一棵包含 $n$ 个节点的无向树，节点编号为 $1$ 到 $n$。你需要为每个节点 $i$ 分配一个非负整数 $a_i$，满足 $0 \le a_i < 2^{30}$。

每条边 $(u,v)$ 带有一个权值 $c$，它对该边两端节点施加如下二进制位限制：考虑所有二进制位 $k$（$k \ge 0$），记 $c$ 的第 $k$ 位为 $c_k \in \{0,1\}$，

• 若 $c_k = 1$，则 $a_u$ 与 $a_v$ 的第 $k$ 位都必须为 $1$；
• 若 $c_k = 0$，则 $a_u$ 与 $a_v$ 的第 $k$ 位不能同时为 $1$。

你的目标是在满足所有边限制的前提下，最大化所有节点值之和 $\sum_{i=1}^n a_i$，并输出该最大值。

数据保证至少存在一种合法分配方案。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写