【题解】[TJOI2018] 异或 可持久化 01 Trie ——quhengyi11

传送门

因为好久没打可持久化的东西了所以拿这个来练练手

思路很简单。

对于子树的操作就是在 $dfs$序上的一个区间操作，在那个区间建立可持久化 $Trie$即可。

对于路径的操作，你可以在树上建 $Trie$，类似树上差分的思想。你首先需要写一个 $lca=(u,v)$，然后就是查询 $(u,lca)$和 $(fa[lca],v)$的最大值就行了。

大概写了快两个小时，中间调自闭了一会儿，果然 $qhy$码力太差了，不过估计是写太慢了然后就 $1A$了。

#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 10086
#define lowbit(x) (x & -x)
#define N 100005
#define ls (u << 1)
#define rs (u << 1 | 1)
#define cl(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
inline void read (int &x)
{
    x = 0;
    Re char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
}
int head[N], tot, tim, out[N], fa[N][18], dep[N], in[N], n, m, a[N], dfn[N];
struct edge {
    int nxt, v;
} e[N << 1];
inline void addedge (int u, int v)
{
    e[++tot] = (edge) {head[u], v};
    head[u] = tot;
}
struct trie {
    int rt[N], t[N << 5][2], cnt, sum[N << 5];
    inline void ins (int &uu, int pu, int val)
    {
        uu = ++cnt;
        int u = uu;
        sum[u] = sum[pu] + 1;
        fd (i, 29, 0)
        {
            bool now = (val >> i & 1);
            t[u][now] = ++cnt;
            t[u][!now] = t[pu][!now];
            pu = t[pu][now]; u = t[u][now];
            sum[u] = sum[pu] + 1;
        }
    }
    inline int query (int u, int pu, int val)
    {
        int ret = 0;
        fd (i, 29, 0)
        {
            bool now = (val >> i & 1);
            if (sum[t[u][!now]] - sum[t[pu][!now]])
            {
                ret |= 1 << i;
                u = t[u][!now];
                pu = t[pu][!now];
            }
            else
            {
                u = t[u][now];
                pu = t[pu][now];
            }
        }
        return ret;
    }
} t1, t2;
inline void dfs (int u, int FA)
{
    fa[u][0] = FA;
    dep[u] = dep[FA] + 1;
    t1.ins(t1.rt[u], t1.rt[FA], a[u]);
    fo (i, 1, 16) 
    {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
        if (!fa[u][i]) break;
    }
    in[u] = ++tim; dfn[tim] = u;
    edge (i, u)
    {
        if (v == FA) continue;
        dfs(v, u);
    }
    out[u] = tim;
}
inline int getlca (int u, int v)
{
    if (dep[u] < dep[v]) std::swap(u, v);
    int delta = dep[u] - dep[v];
    fo (i, 0, 16)
    {
        if (delta >> i & 1)
        {
            u = fa[u][i];
            delta ^= 1 << i;
            if (!delta) break;
        }
    }
    if (u == v) return u;
    fd (i, 16, 0)
        if (fa[u][i] != fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    return fa[u][0];
}
int main ()
{
    read(n); read(m);
    fo (i, 1, n) read(a[i]);
    fo (i, 2, n)
    {
        int u, v;
        read(u); read(v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, 0);
    fo (i, 1, n) t2.ins(t2.rt[i], t2.rt[i - 1], a[dfn[i]]);
    while (m--)
    {
        int opt, x, y, z;
        read(opt); read(x); read(y);
        if (opt == 2)
        {
            read(z);
            int lca = getlca(x, y);
            int ans = std::max(t1.query(t1.rt[x], t1.rt[lca], z), t1.query(t1.rt[y], t1.rt[fa[lca][0]], z));
            printf("%d\n", ans);
        }
        else
        {
            printf("%d\n", t2.query(t2.rt[out[x]], t2.rt[in[x] - 1], y));
        }
    }
    return 0;
}