洛谷 P3292 [SCOI2016]幸运数字

https://www.luogu.com.cn/problem/P3292

多次询问求一条链取若干点的最大异或和

考虑一个集合的最大异或和可以求出线性基完成，两个集合的线性基可以合并，但是线性基并没有可减性，于是我们求 lca 的时候只能每次往集合里添加一条链，为了保证复杂度只能用倍增做。

std::vector<i64> merge(std::vector<i64> a, std::vector<i64> b) {
	std::vector<i64> c = a;
	for (int i = 60; i >= 0; i--) {
		i64 t = b[i];
		for (int j = 60; j >= 0; j--) {
			if (!t) break; if ((t >> j & 1) == 0) continue;
			if (!c[j]) c[j] = t; t ^= c[j];
		}
	}
	return c;
}

int main() {
	int n = read(), Q = read(); i64 val[n + 1];
	std::vector<int> edge[n + 1];
	for (int i = 1; i <= n; i++) val[i] = read();
	edge[1].push_back(0);
	for (int i = 1; i < n; i++) {
		int u = read(), v = read();
		edge[u].push_back(v); edge[v].push_back(u);
	}
	int fa[n + 1][20] = {0}, dep[n + 1] = {0};
	std::vector<i64> box[n + 1][20];
	std::function<void(int, int)> dfs = [&](int u, int last) -> void {
		dep[u] = dep[last] + 1;
		for (auto v : edge[u]) {
			if (v == last) {
				fa[u][0] = v; box[u][0].resize(61);
				for (int j = 60; j >= 0; j--) {
					if ((val[u] >> j & 1) == 0) {box[u][0][j] = val[u]; break;}
				}
				for (int j = 1; j <= 18; j++) {
					int F = fa[u][j - 1];
					if (!F || !fa[F][j - 1]) break;
					fa[u][j] = fa[F][j - 1];
					box[u][j] = merge(box[u][j - 1], box[F][j - 1]);
				}
				break;
			}
		}
		for (auto v : edge[u]) {
			if (v == last) continue; dfs(v, u);
		}
	};
	dfs(1, 0);
	while (Q--) {
		std::vector<i64> boxx(61, 0);
		int x = read(), y = read();
		if (dep[x] < dep[y]) std::swap(x, y);
		int t = dep[x] - dep[y], p = 0;
		while (t) {
			if (t & 1) {
				boxx = merge(boxx, box[x][p]); x = fa[x][p];
			}
			t >>= 1; p++;
		}
		if (x != y) {
			for (int i = 18; i >= 0; i--) {
				if (fa[x][i] == fa[y][i]) continue;
				boxx = merge(boxx, box[x][i]);
				boxx = merge(boxx, box[y][i]);
				x = fa[x][i]; y = fa[y][i];
			}
			boxx = merge(boxx, box[x][0]);
			boxx = merge(boxx, box[y][0]);
			x = fa[x][0];
		}
		boxx = merge(boxx, box[x][0]);
		i64 ans = 0;
		for (int i = 60; i >= 0; i--) {
			ans = std::max(ans, ans ^ boxx[i]);
		}
		printf("%lld\n", ans);
	}
}