模板及讲解
字典树
字典树是前缀树，支持$insert(s)$和$query(s)$操作
两个函数按照树结构往下走处理即可
维护二进制 (Xor)
给定一棵$n$个点的带权无向树，求树上路径异或和的最大值。
利用 Xor 性质，我们发现路径异或和满足容斥 (即$[l,r]$可由$[1,r]，[1, l-1]$得出)
那么我们求根到每个点的异或和$d_i$，然后尝试如何异或出一条路径来
我们发现任意两个$d_i,d_j$的异或和为某条路径的异或和，且不漏解
那么问题转化为求序列$d_i$两两异或最大值。
因为 Xor 常用 Trie 维护，所以我们可以运用 Trie 求这个最大值。将所有$d_i$以二进制形式插入 Trie (高位在上，定一个最大位数，不够在前面补0)，边权为二进制位，然后对于每个二进制下的$d_i$在Trie树上走尽量相反的边，因为这样保证异或后大。树上没有最优边那就只能走另一条边。这样下来的路径就是$d_i$与其他$d_j$的最大异或值。$O(n \cdot len)$操作即可，$len$为二进制最大位数。
常见题型
Trie树：
1、前缀问题
2、翻转字符串，处理后缀 jzoj 5397，bzoj 4567
3、01Trie：Xor问题 CF 842D，poj 3764
4、回文相关：Bzoj 1524 (多个回文串拼接问题)
Trie图：AC自动机
Fail树：bzoj 2938
前缀关系树 (Trie树去除虚节点) bzoj 4567
可持久化Trie树相关代码
差分版
https://www.luogu.org/problem/P4592
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 3, LEN = 30;
int n, Q, vi[MAXN], idx, dfn[MAXN], l[MAXN], r[MAXN], fa[MAXN], pre[MAXN][22], dep[MAXN];
vector<int > G[MAXN];
int rt_1[MAXN], ch_1[MAXN * 33][2], cnt_1, siz_1[MAXN * 33];
int rt_2[MAXN], ch_2[MAXN * 33][2], cnt_2, siz_2[MAXN * 33];
void dfs(int u, int p) {
fa[u] = p, dfn[++idx] = u, l[u] = idx;
pre[u][0] = p, dep[u] = dep[p] + 1;
for (int i = 1; i <= 20; ++i) pre[u][i] = pre[pre[u][i - 1]][i - 1];
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != p) dfs(v, u);
}
r[u] = idx;
}
int LCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i = 20; i >= 0; --i) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
if (a == b) return a;
for (int i = 20; i >= 0; --i) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
void ins_1(int pre, int now, int i, int a) {
siz_1[now] = siz_1[pre];
if (i == -1) {siz_1[now]++; return ;}
int c = (a >> i) & 1;
ch_1[now][c] = ++cnt_1, ch_1[now][c ^ 1] = ch_1[pre][c ^ 1];
ins_1(ch_1[pre][c], ch_1[now][c], i - 1, a);
siz_1[now] += siz_1[ch_1[now][0]] + siz_1[ch_1[now][1]];
}
void ins_2(int pre, int now, int i, int a) {
siz_2[now] = siz_2[pre];
if (i == -1) {siz_2[now]++; return ;}
int c = (a >> i) & 1;
ch_2[now][c] = ++cnt_2, ch_2[now][c ^ 1] = ch_2[pre][c ^ 1];
ins_2(ch_2[pre][c], ch_2[now][c], i - 1, a);
siz_2[now] += siz_2[ch_2[now][0]] + siz_2[ch_2[now][1]];
}
int query_1(int pre, int now, int b) {
int bs = (1 << LEN), ret = 0;
for (int i = LEN; i >= 0; --i) {
int c = (b >> i) & 1, whw = siz_1[ch_1[now][c ^ 1]] - siz_1[ch_1[pre][c ^ 1]];
if (whw) ret += bs, pre = ch_1[pre][c ^ 1], now = ch_1[now][c ^ 1];
else pre = ch_1[pre][c], now = ch_1[now][c];
bs /= 2;
}
return ret;
}
int query_2(int u, int v, int lca, int flca, int b) {
int bs = (1 << LEN), ret = 0;
for (int i = LEN; i >= 0; --i) {
int c = (b >> i) & 1, whw = siz_2[ch_2[u][c ^ 1]] + siz_2[ch_2[v][c ^ 1]] - siz_2[ch_2[lca][c ^ 1]] - siz_2[ch_2[flca][c ^ 1]];
if (whw) ret += bs, u = ch_2[u][c ^ 1], v = ch_2[v][c ^ 1], lca = ch_2[lca][c ^ 1], flca = ch_2[flca][c ^ 1];
else u = ch_2[u][c], v = ch_2[v][c], lca = ch_2[lca][c], flca = ch_2[flca][c];
bs /= 2;
}
return ret;
}
void clean() {
}
int solve() {
clean();
cin >> n >> Q;
for (int i = 1; i <= n; ++i) scanf("%d", &vi[i]);
for (int x, y, i = 1; i < n; ++i) scanf("%d%d", &x, &y), G[x].push_back(y), G[y].push_back(x);
dfs(1, 0);
for (int i = 1; i <= n; ++i) {
ins_1(rt_1[i - 1], rt_1[i] = ++cnt_1, LEN, vi[dfn[i]]);
ins_2(rt_2[fa[i]], rt_2[i] = ++cnt_2, LEN, vi[i]);
}
while (Q--) {
int tp; scanf("%d", &tp);
if (tp == 1) {
int x, gg; scanf("%d%d", &x, &gg);
printf("%d\n", query_1(rt_1[l[x] - 1], rt_1[r[x]], gg));
} else {
int x, y, gg; scanf("%d%d%d", &x, &y, &gg);
int l = LCA(x, y);
printf("%d\n", query_2(rt_2[x], rt_2[y], rt_2[l], rt_2[fa[l]], gg));
}
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
