不正常国家

一棵树，两点间的路径长度定义为经过点权值的异或和。对于每个点 \(i\), 求：

先求根缀异或和 \(a\),这样 \(dis(u,v)=a[u]\text{^} a[v] \text{^} a[lca(u,v)]\)

看到异或容易想到01trie合并，和线段树合并方法一样，每个点 \(i\) 开个01trie往上合并，同时在两棵01trie中查异或起来异或 \(a[i]\) 最大的数(详见代码)。

直接交上去T掉，用启发式合并，先处理重儿子，再处理轻儿子就行了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100005;

struct node {
	node *ch[2];
	inline node () {
		ch[0] = ch[1] = NULL;
	}
} poor[N * 64];

node *root[N];

int en = 0, top = 0;

struct edge {
	int head, to, nxt;
} ed[N << 1];

inline void addedge(int from, int to) {
	ed[++en].to = to; ed[en].nxt = ed[from].head; ed[from].head = en;
}

int a[N], ans[N];

inline void insert(node *rt, int p) {
	node *cur = rt;
	if (cur == NULL) cur = &poor[top++];
	for (register int i = 31; ~i; --i) {
		int t = (p >> i) & 1;
		if (cur -> ch[t] == NULL) (cur -> ch[t]) = &poor[top++];
		cur = cur -> ch[t];
	}
}

inline int max_(int a, int b) {
	return a > b ? a : b;
}

inline int get(node *rta, node *rtb, int dep, int p) {
	if (rta == NULL || rtb == NULL) return 0;
	if (dep < 0) return 0;
	int ans = 0, flag = 0, t = (p >> dep) & 1;
	if (rta -> ch[0] != NULL) {
		if (rtb -> ch[1 ^ t] != NULL) ans = get(rta -> ch[0], rtb -> ch[1 ^ t], dep - 1, p) + (1 << dep), flag = 1;
		else ans = get(rta -> ch[0], rtb -> ch[0 ^ t], dep - 1, p);
	}
	if (rta -> ch[1] != NULL) {
		if (rtb -> ch[0 ^ t] != NULL) ans = max_(ans, get(rta -> ch[1], rtb -> ch[0 ^ t], dep - 1, p) + (1 << dep));
		else if (!flag) ans = max_(ans, get(rta -> ch[1], rtb -> ch[1 ^ t], dep - 1, p));
	} return ans;
}

inline node* merge(node *rta, node *rtb) {
	if (rta == NULL) return rtb;
	if (rtb == NULL) return rta;
	node *ret = &poor[top++];
	ret -> ch[0] = merge(rta -> ch[0], rtb -> ch[0]);
	ret -> ch[1] = merge(rta -> ch[1], rtb -> ch[1]);
	return ret;
}

int siz[N];

inline void dfs(int now, int fa) {
	root[now] = &poor[top++]; siz[now] = 1; int zson = 0;
	int t = ans[now] = a[now]; a[now] ^= a[fa]; insert(root[now], a[now]);
	for (register int i = ed[now].head; i; i = ed[i].nxt) {
		int v = ed[i].to; if (v == fa) continue; 
		dfs(v, now); siz[now] += siz[v];
		if (siz[v] > siz[zson]) zson = v;
//		root[now] = merge(root[now], root[v]);
//		ans[now] = max_(ans[now], get(root[v], root[now], 31, t));
	}if (zson) {
		ans[now] = max_(ans[now], get(root[now], root[zson], 31, t));
		root[now] = merge(root[now], root[zson]);
	}
	for (register int i = ed[now].head; i; i = ed[i].nxt) {
		int v = ed[i].to; if (v == fa) continue; 
		if (v != zson) {
			ans[now] = max_(ans[now], get(root[v], root[now], 31, t));
			root[now] = merge(root[now], root[v]);
		}
	} 
}

int n, u, v;

inline int read() {
	register int s = 0;
	register char ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch & 15), ch = getchar();
	return s;
}

inline void otp(int a) {
	a >= 10 ?  otp(a / 10), putchar((a % 10) ^ 48) : putchar(a ^ 48);
}

int main() {
	freopen("irregular.in", "r", stdin);freopen("irregular.out", "w", stdout);
	n = read();
	for (register int i = 1; i <= n; ++i) a[i] = read();
	for (register int i = 1; i < n; ++i) {
		u = read(); v = read();
		addedge(u, v); addedge(v, u);
	} a[0] = 0; dfs(1, 0);
	for (register int i = 1; i <= n; ++i) otp(ans[i]), putchar(‘ ‘);
	fclose(stdin); fclose(stdout); return 0;
}

不正常国家

原文：https://www.cnblogs.com/wwlwakioi/p/14640423.html