bzoj 5338: [TJOI2018]xor

题意：

给你一颗树，点上有权值，你要在子树中或路径中找到一个值使得$z$异或它最大。

题解：

又双叒叕看错题了。。
直接建两个可持久化trie，一颗按dfs序开，一颗按到根的路径开，再求个lca，做完了。

代码：

#include <bits/stdc++.h>
using namespace std;

int n, q, num = 0, fst[100010], a[100010], l[100010], r[100010], nn = 0;
struct trie
{
    trie *s[2];
    int cnt;
    trie() : cnt(0), s() {}
} *root1[100010], *root2[100010];
struct edge
{
    int x, y, n;
} e[200010];
struct pnt
{
    int fa[17], dep;
} p[100010];

trie *insert(trie *last, int x)
{
    trie *root = new trie(*last);
    trie *now = root;
    for (int i = 30; i >= 0; i--)
    {
        now->cnt++;
        bool hh = x & (1 << i);
        if (now->s[hh]) now->s[hh] = new trie(*now->s[hh]);
        else now->s[hh] = new trie();
        now = now->s[hh];
    }
    now->cnt++;
    return root;
}
void ins(int x, int y)
{
    e[++num] = {x, y, fst[x]};
    fst[x] = num;
}
void dfs(int x, int fa)
{
    p[x].dep = p[fa].dep + 1;
    l[x] = ++nn;
    root1[x] = insert(root1[fa], a[x]);
    root2[l[x]] = insert(root2[l[x] - 1], a[x]);
    p[x].fa[0] = fa;
    for (int i = 1; i <= 16; i++)
        p[x].fa[i] = p[p[x].fa[i - 1]].fa[i - 1];
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (y == fa) continue;
        dfs(y, x);
    }
    r[x] = nn;
}
int get_lca(int x, int y)
{
    if (p[x].dep < p[y].dep) swap(x, y);
    for (int i = 16; i >= 0; i--)
        if ((1 << i) <= p[x].dep - p[y].dep)
            x = p[x].fa[i];
    if (x == y) return x;
    for (int i = 16; i >= 0; i--)
        if (p[x].fa[i] != p[y].fa[i])
        {
            x = p[x].fa[i];
            y = p[y].fa[i];
        }
    return p[x].fa[0];
}
int wk(trie *last, trie *now, int x)
{
    for (int i = 30; i >= 0 && now; i--)
    {
        bool hh = !(x & (1 << i));
        if (now->s[hh] && (!last || !last->s[hh] || last->s[hh]->cnt < now->s[hh]->cnt))
        {
            now = now->s[hh];
            if (last) last = last->s[hh];
            x ^= (hh << i);
        }
        else
        {
            hh ^= 1;
            now = now->s[hh];
            if (last) last = last->s[hh];
            x ^= (hh << i);
        }
    }
    return x;
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ins(x, y);
        ins(y, x);
    }
    root1[0] = new trie();
    root2[0] = new trie();
    dfs(1, 0);
    while (q--)
    {
        int op;
        scanf("%d", &op);
        if (op == 1)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", wk(root2[l[x] - 1], root2[r[x]], y));
        }
        else
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            int lca = get_lca(x, y);
            printf("%d\n", max(wk(root1[p[lca].fa[0]], root1[x], z), wk(root1[p[lca].fa[0]], root1[y], z)));
        }
    }
}