自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 23:01:22，当前版本为作者最后更新于2024-07-21 16:40:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑不在树上咋做。先给序列排序，然后一个一个判是否有 $a_{i-1}+a_i>a_{i+1}$。
如果不满足要求的话，那么对于所有 $1<i<n$ 都有 $a_{i-1}+a_i\le a_{i+1}$。最小情况下 $a_{i+1}=a_i+a_{i-1}$，$a_1=a_2=1$。此时 $a_i=f_i$。但是你会发现 $f_{46}>2^{31}-1$，也就是说 $n\ge46$ 就必定有解，非常 amazing 啊！只要对 $<46$ 的区间暴力即可。
回到原题，查询只要先判路径长度再暴力跳即可。这部分是简单的，压力给到链异或单点查询。
容易发现，每次修改都能拆成四次到根链的修改。具体地，设 $k=\operatorname{lca}(u,v)$，则 $u\to v$ 异或上 $w$ 相当于 $1\to u,1\to v,1\to k,1\to fa_k$ 异或上 $w$。但还是不好看，继续差分一下就能变成单点异或子树查，在 dfn 上建个树状数组即可。时间复杂度 $O(n\log n+m\log n + mC\log C)$，其中 $C=46$。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

vector<int> g[MAXN];

int n, a[MAXN], dep[MAXN], fa[20][MAXN];

int c[MAXN], in[MAXN], out[MAXN], id;

void init(int u, int f) {
	fa[0][u] = f, dep[u] = dep[f] + 1, in[u] = ++id, a[f] ^= a[u];
	for (int i = 1; i <= __lg(dep[u]); i++) fa[i][u] = fa[i - 1][fa[i - 1][u]];
	for (int v : g[u]) if (v != f) init(v, u); out[u] = id;
}

inline 
void add(int u, int x) {
	for (int i = in[u]; i <= n; i += i & -i) c[i] ^= x;
}

inline 
int ask(int u) {
	int res = 0;
	for (int i = out[u]; i; i &= i - 1) res ^= c[i];
	for (int i = in[u] - 1; i; i &= i - 1) res ^= c[i];
	return res;
}

inline 
int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (; dep[u] > dep[v]; u = fa[__lg(dep[u] - dep[v])][u]);
	if (u == v) return u;
	for (int i = __lg(dep[u]); ~i; i--) {
		if (fa[i][u] != fa[i][v]) u = fa[i][u], v = fa[i][v];
	}
	return fa[0][u];
}

inline 
vector<int> get(int u, int v) {
	vector<int> d;
	if (dep[u] < dep[v]) swap(u, v);
	for (; dep[u] > dep[v]; d.emplace_back(ask(u)), u = fa[0][u]);
	for (; u != v; ) {
		d.emplace_back(ask(u)), u = fa[0][u];
		d.emplace_back(ask(v)), v = fa[0][v];
	}
	return d.emplace_back(ask(u)), d;
}

inline 
bool check(vector<int> d) {
	sort(d.begin(), d.end()); int m = d.size();
	for (int i = 1; i < m - 1; i++) {
		if (d[i - 1] > d[i + 1] - d[i]) return 1;
	}
	return 0;
}

inline 
void modify(int u, int v, int w) {
	int k = lca(u, v);
	add(u, w), add(v, w), add(k, w);
	if (fa[0][k]) add(fa[0][k], w);
}

inline 
bool query(int u, int v) {
	int k = lca(u, v);
	if (dep[u] + dep[v] - 2 * dep[k] + 1 > 46) return 1;
	else return check(get(u, v));
}

int m;

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1, u, v; i < n; i++) {
		scanf("%d%d", &u, &v);
		g[u].emplace_back(v), g[v].emplace_back(u);
	}
	init(1, 0);
	for (int i = 1; i <= n; i++) add(i, a[i]);
	for (int opt, u, v, w; m--;) {
		scanf("%d%d%d", &opt, &u, &v);
		if (opt == 1) scanf("%d", &w), modify(u, v, w);
		else printf("%d", query(u, v));
	}
}