思路与证明

• 按位分治

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

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

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

• 强制赋值与森林独立集

  • 先找出所有在该位上被“$1$-边”强制为 $1$ 的点，记为“强制 $1$”。这些点的所有“$0$-边”邻居都被强制为 $0$（记为“强制 $0$”），否则会与按位与为 $0$ 的限制矛盾（数据保证无矛盾）。

  • 去掉所有“强制 $1$”点，仅保留“$0$-边”构成的子图（是森林，因为原图是树的子图）。在这片森林上做最大独立集：

    • “强制 $0$”点不可取；
    • 其余自由点可以按独立集规则择取。

• 树形 DP 转移（在该位的“$0$-边”森林上）

  • 定义 $dp0[u]$：$u$ 取 $0$ 时子树内最多取 $1$ 的个数；

  • 定义 $dp1[u]$：$u$ 取 $1$ 时子树内最多取 $1$ 的个数；

  • 若 $u$ 为“强制 $1$”，该点不进入森林 DP（其贡献另行累计）；

  • 若 $u$ 为“强制 $0$”，则 $dp1[u] = -\infty$，$dp0[u] = \sum \max(dp0[v], dp1[v])$；

  • 若 $u$ 为自由点，则

    • $dp1[u] = 1 + \sum dp0[v]$（与“$0$-边”相邻点不能同时为 $1$）；
    • $dp0[u] = \sum \max(dp0[v], dp1[v])$。

• 该位的总贡献

  • 设该位强制为 $1$ 的点个数为 $C_1$，森林 DP 的最大独立集大小为 $C_{\text{free}}$，该位贡献为 $(C_1 + C_{\text{free}})\times 2^b$。

• 总复杂度

  • 共处理 $30$ 个比特位，每次在线性时间内完成，时间复杂度为 $O(30n)$，空间复杂度为 $O(n)$。

C++

#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int u, v;
	int w;
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	if (!(cin >> n)) return 0;
	vector<Edge> edges;
	edges.reserve(n - 1);
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		int w;
		cin >> u >> v >> w;
		edges.push_back({u, v, w});
	}

	long long ans = 0;
	const long long NEG = (long long)-4e18;

	// 对每一位独立处理
	for (int b = 0; b < 30; ++b) {
		vector<char> forced1(n + 1, 0), forced0(n + 1, 0);
		vector<vector<int>> zeroAdj(n + 1);

		// 建“0-边”邻接，同时标出强制为1的点
		for (const auto &e : edges) {
			if ((e.w >> b) & 1) {
				forced1[e.u] = 1;
				forced1[e.v] = 1;
			} else {
				zeroAdj[e.u].push_back(e.v);
				zeroAdj[e.v].push_back(e.u);
			}
		}

		// 强制0：与强制1通过“0-边”相邻的点必须为0
		for (int u = 1; u <= n; ++u) if (forced1[u]) {
			for (int v : zeroAdj[u]) {
				forced0[v] = 1;
			}
		}

		long long countForced1 = 0;
		for (int u = 1; u <= n; ++u) if (forced1[u]) ++countForced1;

		// 在仅包含“0-边”的森林上做树形DP（跳过强制1的点）
		vector<char> vis(n + 1, 0);
		vector<long long> dp0(n + 1, 0), dp1(n + 1, 0);
		long long addFree = 0;

		for (int s = 1; s <= n; ++s) {
			if (forced1[s] || vis[s]) continue;

			// 迭代DFS（两阶段：入栈/出栈）以避免递归
			struct Item { int u, p, st; };
			vector<Item> st;
			st.reserve(64);
			st.push_back({s, 0, 0});
			vis[s] = 1;

			while (!st.empty()) {
				auto cur = st.back();
				st.pop_back();
				int u = cur.u, p = cur.p, state = cur.st;

				if (state == 0) {
					// 进入：稍后回溯计算，先压出栈标记
					st.push_back({u, p, 1});
					for (int v : zeroAdj[u]) {
						if (v == p || forced1[v] || vis[v]) continue;
						vis[v] = 1;
						st.push_back({v, u, 0});
					}
				} else {
					// 回溯：计算dp
					long long take0 = 0;
					long long take1 = forced0[u] ? NEG : 1;
					for (int v : zeroAdj[u]) {
						if (v == p || forced1[v]) continue;
						// v 已经在回溯阶段计算好
						long long c0 = dp0[v], c1 = dp1[v];
						take0 += max(c0, c1);
						if (take1 > NEG / 2) take1 += c0; // 若u=1，孩子必须取0
					}
					dp0[u] = take0;
					dp1[u] = take1;

					// 若是该连通分量根，累计贡献
					if (p == 0) {
						addFree += max(dp0[u], dp1[u]);
					}
				}
			}
		}

		long long ones = countForced1 + addFree;
		ans += ones * (1LL << b);
	}

	cout << ans << '\n';
	return 0;
}

Python

import sys

def main():
	data = sys.stdin.read().strip().split()
	if not data:
		return
	it = iter(data)
	n = int(next(it))
	edges = []
	for _ in range(n - 1):
		u = int(next(it)); v = int(next(it)); w = int(next(it))
		edges.append((u, v, w))

	ans = 0
	NEG = -10**18

	for b in range(30):
		forced1 = [False] * (n + 1)
		forced0 = [False] * (n + 1)
		zeroAdj = [[] for _ in range(n + 1)]

		# 构建“0-边”邻接表并标记强制1
		for (u, v, w) in edges:
			if (w >> b) & 1:
				forced1[u] = True
				forced1[v] = True
			else:
				zeroAdj[u].append(v)
				zeroAdj[v].append(u)

		# 强制0：通过“0-边”与强制1相邻的点必须取0
		for u in range(1, n + 1):
			if forced1[u]:
				for v in zeroAdj[u]:
					forced0[v] = True

		countForced1 = sum(1 for u in range(1, n + 1) if forced1[u])

		# 在“0-边”森林上做树形DP（迭代）
		vis = [False] * (n + 1)
		dp0 = [0] * (n + 1)
		dp1 = [0] * (n + 1)
		addFree = 0

		for s in range(1, n + 1):
			if forced1[s] or vis[s]:
				continue

			# 栈元素：(u, parent, state)；state=0入栈、1出栈
			stack = [(s, 0, 0)]
			vis[s] = True

			while stack:
				u, p, stt = stack.pop()
				if stt == 0:
					stack.append((u, p, 1))
					for v in zeroAdj[u]:
						if v == p or forced1[v] or vis[v]:
							continue
						vis[v] = True
						stack.append((v, u, 0))
				else:
					take0 = 0
					take1 = 1 if not forced0[u] else NEG
					for v in zeroAdj[u]:
						if v == p or forced1[v]:
							continue
						c0, c1 = dp0[v], dp1[v]
						take0 += c0 if c0 >= c1 else c1
						if take1 > NEG // 2:
							take1 += c0
					dp0[u] = take0
					dp1[u] = take1
					if p == 0:
						addFree += dp0[u] if dp0[u] >= dp1[u] else dp1[u]

		ones = countForced1 + addFree
		ans += ones * (1 << b)

	print(ans)

if __name__ == "__main__":
	# 提升递归深度对本题无用，因为我们使用迭代DFS
	main()

Java

import java.io.*;
import java.util.*;

// 快速读入
class FastScanner {
	BufferedInputStream in;
	byte[] buffer = new byte[1 << 16];
	int ptr = 0, len = 0;
	FastScanner(InputStream is) { in = new BufferedInputStream(is); }
	int read() throws IOException {
		if (ptr >= len) {
			len = in.read(buffer);
			ptr = 0;
			if (len <= 0) return -1;
		}
		return buffer[ptr++];
	}
	int nextInt() throws IOException {
		int c, s = 1, x = 0;
		do { c = read(); } while (c <= 32);
		if (c == '-') { s = -1; c = read(); }
		while (c > 32) { x = x * 10 + (c - '0'); c = read(); }
		return x * s;
	}
}

public class Main {
	static class Edge {
		int u, v, w;
		Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
	}
	static class Item {
		int u, p, st;
		Item(int u, int p, int st) { this.u = u; this.p = p; this.st = st; }
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		int n = fs.nextInt();
		ArrayList<Edge> edges = new ArrayList<>(Math.max(1, n - 1));
		for (int i = 0; i < n - 1; ++i) {
			int u = fs.nextInt(), v = fs.nextInt(), w = fs.nextInt();
			edges.add(new Edge(u, v, w));
		}

		long ans = 0L;
		final long NEG = (long)-4e18;

		// 对每一位独立处理
		for (int b = 0; b < 30; ++b) {
			boolean[] forced1 = new boolean[n + 1];
			boolean[] forced0 = new boolean[n + 1];
			@SuppressWarnings("unchecked")
			ArrayList<Integer>[] zeroAdj = new ArrayList[n + 1];
			for (int i = 1; i <= n; ++i) zeroAdj[i] = new ArrayList<>();

			// 标记强制1，并建立“0-边”邻接
			for (Edge e : edges) {
				if (((e.w >> b) & 1) == 1) {
					forced1[e.u] = true;
					forced1[e.v] = true;
				} else {
					zeroAdj[e.u].add(e.v);
					zeroAdj[e.v].add(e.u);
				}
			}

			// 强制0
			for (int u = 1; u <= n; ++u) if (forced1[u]) {
				for (int v : zeroAdj[u]) forced0[v] = true;
			}

			long countForced1 = 0;
			for (int u = 1; u <= n; ++u) if (forced1[u]) ++countForced1;

			// 在“0-边”森林上做树形DP
			boolean[] vis = new boolean[n + 1];
			long[] dp0 = new long[n + 1];
			long[] dp1 = new long[n + 1];
			long addFree = 0;

			ArrayDeque<Item> st = new ArrayDeque<>();

			for (int s = 1; s <= n; ++s) {
				if (forced1[s] || vis[s]) continue;

				st.clear();
				st.push(new Item(s, 0, 0));
				vis[s] = true;

				while (!st.isEmpty()) {
					Item cur = st.pop();
					int u = cur.u, p = cur.p, state = cur.st;

					if (state == 0) {
						st.push(new Item(u, p, 1));
						for (int v : zeroAdj[u]) {
							if (v == p || forced1[v] || vis[v]) continue;
							vis[v] = true;
							st.push(new Item(v, u, 0));
						}
					} else {
						long take0 = 0;
						long take1 = forced0[u] ? NEG : 1;
						for (int v : zeroAdj[u]) {
							if (v == p || forced1[v]) continue;
							long c0 = dp0[v], c1 = dp1[v];
							take0 += Math.max(c0, c1);
							if (take1 > NEG / 2) take1 += c0;
						}
						dp0[u] = take0;
						dp1[u] = take1;
						if (p == 0) {
							addFree += Math.max(dp0[u], dp1[u]);
						}
					}
				}
			}

			long ones = countForced1 + addFree;
			ans += ones * (1L << b);
		}

		System.out.println(ans);
	}
}

题目内容

给定一棵包含 $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