526互联

CodeForces 1902F Trees and XOR Queries Again

发布时间 2023-12-10 12:21:12作者: zltzlt

洛谷传送门

CF 传送门

如果我们能把 \(x \to y\) 路径上的所有点权插入到线性基，那么可以 \(O(\log V)\) 查询。

但是因为线性基合并只能 \(O(\log^2 V)\)（把一个线性基的所有元素插入到另一个），所以只能倍增做 \(O((n + q) \log n \log^2 V)\)，过不了。

考虑 \(O(n \log V)\) 预处理出每个点到根的所有点权的线性基 \(f_u\)，那么对于一个询问，把 \(f_x\) 和 \(f_y\) 合并，再抠掉 \(\text{lca}(x, y)\) 以上部分的点权即可。

但是线性基不支持删除，考虑贪心地在不影响线性基能组成的数的前提下，每个 \(f_u\) 中保留深度最大的点的点权（就是 CF1100F Ivan and Burgers 第一篇题解）。查询只考虑深度 \(\ge dep_{\text{lca}(x, y)}\) 的元素即可。

于是时间复杂度降至 \(O((n + q \log V) \log V)\)（瓶颈在合并线性基），可过。

code 
// Problem: F. Trees and XOR Queries Again
// Contest: Codeforces - Educational Codeforces Round 159 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1902/problem/F
// Memory Limit: 512 MB
// Time Limit: 6500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar();
    int x = 0;
    for (; !isdigit(c); c = getchar()) ;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x;
}

const int maxn = 200100;
const int logn = 20;

int n, m, a[maxn];
vector<int> G[maxn];

struct Basis {
	int p[20], q[20];
	
	inline void insert(int x, int y) {
		for (int i = 19; ~i; --i) {
			if (x & (1 << i)) {
				if (!p[i]) {
					p[i] = x;
					q[i] = y;
					break;
				} else if (q[i] < y) {
					swap(p[i], x);
					swap(q[i], y);
				}
				x ^= p[i];
			}
		}
	}
	
	inline bool check(int x, int y) {
		for (int i = 19; ~i; --i) {
			if ((x & (1 << i)) && y <= q[i]) {
				x ^= p[i];
			}
		}
		return !x;
	}
} g[maxn];

inline Basis operator + (const Basis &a, const Basis &b) {
	Basis res = a;
	for (int i = 0; i < 20; ++i) {
		if (b.p[i]) {
			res.insert(b.p[i], b.q[i]);
		}
	}
	return res;
}

int fa[maxn], sz[maxn], son[maxn], dep[maxn], top[maxn];

int dfs(int u, int f, int d) {
	fa[u] = f;
	sz[u] = 1;
	dep[u] = d;
	g[u] = g[f];
	g[u].insert(a[u], dep[u]);
	int mx = -1;
	for (int v : G[u]) {
		if (v == f) {
			continue;
		}
		sz[u] += dfs(v, u, d + 1);
		if (sz[v] > mx) {
			son[u] = v;
			mx = sz[v];
		}
	}
	return sz[u];
}

void dfs2(int u, int tp) {
	top[u] = tp;
	if (!son[u]) {
		return;
	}
	dfs2(son[u], tp);
	for (int v : G[u]) {
		if (!top[v]) {
			dfs2(v, v);
		}
	}
}

inline int qlca(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) {
			swap(x, y);
		}
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) {
		swap(x, y);
	}
	return x;
}

void solve() {
	n = read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
	}
	for (int i = 1, u, v; i < n; ++i) {
		u = read();
		v = read();
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1, 0, 1);
	dfs2(1, 1);
	m = read();
	while (m--) {
		int x, y, z;
		x = read();
		y = read();
		z = read();
		int lca = qlca(x, y);
		Basis b = g[x] + g[y];
		puts(b.check(z, dep[lca]) ? "YES" : "NO");
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}