vjudge传送
一句话题意：给一棵树，有(m)次操作，每一次让你从节点(x)到节点(y)的路径中选出一个点，使这个点的权值异或(z)最大。（数据范围(10^5)）
如果是一个序列，那么就是01-Trie的经典应用。
现在是一棵树，就要用到可持久化Trie啦。
可持久化Trie这东西和可持久化线段树非常的像：每一层中只把有改动的孩子建成新节点，其余的节点从以前的树中复制过来。只不过孩子个数从线段树中的两个变成了字符集的大小而已。
查询的时候和线段树一样，记录这个节点的一个权值sum，如果(sum[new]>sum[old-1])，说明在([old,new])中这个节点是存在的。于是仿照链上查找异或最大值的方法在trie上从高位到低位跑下去就好啦。
那么对于这道题来说，(x)到(y)的路径拆成([lca, x])和([lca,y])两条路径，取两者之中的最大值就是答案，
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int N = 17;
const int maxn = 1e5 + 5;
const int maxN = 4e6 + 5;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, m, a[maxn];
struct Edge
{
int nxt, to;
}e[maxn << 1];
int head[maxn], ecnt = -1;
In void addEdge(int x, int y)
{
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
struct Trie
{
int ch[2], sum;
}t[maxN];
int root[maxn], cnt = 0;
In void build(int old, int& now, int x, int d)
{
t[now = ++cnt] = t[old];
t[now].sum++;
if(d < 0) return;
int o = (x >> d) & 1;
build(t[old].ch[o], t[now].ch[o], x, d - 1);
}
In void query(int old, int now, int x, int d, int& ans)
{
if(d < 0) return;
int o = ((x >> d) & 1) ^ 1, Sum = t[t[now].ch[o]].sum - t[t[old].ch[o]].sum;
if(Sum > 0) ans += (1 << d), query(t[old].ch[o], t[now].ch[o], x, d - 1, ans);
else query(t[old].ch[o ^ 1], t[now].ch[o ^ 1], x, d - 1, ans);
}
int fa[N + 2][maxn], dep[maxn];
In void dfs(int now, int _f)
{
build(root[_f], root[now], a[now], N);
for(int i = 1; (1 << i) <= dep[now]; ++i)
fa[i][now] = fa[i - 1][fa[i - 1][now]];
forE(i, now, v)
{
if(v == _f) continue;
dep[v] = dep[now] + 1, fa[0][v] = now;
dfs(v, now);
}
}
In int lca(int x, int y)
{
if(dep[x] < dep[y]) swap(x, y);
for(int i = N; i >= 0; --i)
if(dep[fa[i][x]] >= dep[y]) x = fa[i][x];
if(x == y) return x;
for(int i = N; i >= 0; --i)
if(fa[i][x] ^ fa[i][y]) x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
In void Clear()
{
Mem(head, -1), ecnt = -1;
Mem(fa, 0); //一定要把倍增的数组清零……
for(int i = 0; i <= cnt; ++i)
t[i].ch[0] = t[i].ch[1] = t[i].sum = 0;
Mem(root, 0), cnt = 0;
}
int main()
{
// MYFILE();
Mem(head, -1), ecnt = -1;
while(scanf("%d%d", &n, &m) != EOF)
{
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i < n; ++i)
{
int x = read(), y = read();
addEdge(x, y), addEdge(y, x);
}
dep[1] = 1, dfs(1, 0);
for(int i = 1; i <= m; ++i)
{
int x = read(), y = read(), p = read();
int z = lca(x, y), ans1 = 0, ans2 = 0;
query(root[fa[0][z]], root[x], p, N, ans1), query(root[fa[0][z]], root[y], p, N, ans2);
write(max(ans1, ans2)), enter;
}
Clear();
}
return 0;
}