Luogu P4592 [TJOI2018]异或

/**
 * @Date:   2019-04-13T15:14:58+08:00
 * @Last modified time: 2019-04-13T15:14:59+08:00
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
    int next, to;
}e[A];
int head[A], num;
void add(int fr, int to) {
    e[++num].next = head[fr];
    e[num].to = to;
    head[fr] = num;
}
int n, q, w[A], a, b, c;
int dfn[A], tot, dep[A], siz[A], son[A], fa[A], top[A], ended[A], pre[A], rt[A << 5], cnt, opt;
void prepare(int fr) {
    siz[fr] = 1;
    for (int i = head[fr]; i; i = e[i].next) {
        int ca = e[i].to;
        if (ca == fa[fr]) continue;
        fa[ca] = fr;
        dep[ca] = dep[fr] + 1;
        prepare(ca);
        siz[fr] += siz[ca];
        if (siz[ca] > siz[son[fr]]) son[fr] = ca;
    }
}
void dfs(int fr, int tp) {
    dfn[fr] = ++cnt, pre[cnt] = fr, top[fr] = tp;
    if (son[fr]) dfs(son[fr], tp);
    for (int i = head[fr]; i; i = e[i].next) {
        int ca = e[i].to;
        if (ca == fa[fr] or ca == son[fr]) continue;
        dfs(ca, ca);
    }
    ended[fr] = cnt;
}
int wsw, s[A << 5], ch[A << 5][2];
void insert(int pre, int &now, int val, int dep) {
    now = ++wsw;
    s[now] = s[pre] + 1;
    if (dep < 0) return;
    int pos = (val >> dep) & 1;
    ch[now][pos ^ 1] = ch[pre][pos ^ 1];
    insert(ch[pre][pos], ch[now][pos], val, dep - 1);
}
int ask(int pre, int now, int val, int dep) {
    if (dep < 0) return 0;
    int pos = (val >> dep) & 1;
    if (s[ch[now][pos ^ 1]] - s[ch[pre][pos ^ 1]] > 0) return (1 << dep) + ask(ch[pre][pos ^ 1], ch[now][pos ^ 1], val, dep - 1);
    else return ask(ch[pre][pos], ch[now][pos], val, dep - 1);
}
int query(int x, int y, int val, int ans = 0) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans = max(ans, ask(rt[dfn[top[x]] - 1], rt[dfn[x]], val, 30));
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    ans = max(ans, ask(rt[dfn[y] - 1], rt[dfn[x]], val, 30));
    return ans;
}

int main(int argc, char const *argv[]) {
    scanf("%d%d", &n, &q); dep[1] = 1;
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1; i < n; i++) scanf("%d%d", &a, &b), add(a, b), add(b, a);
    prepare(1); dfs(1, 1);
    for (int i = 1; i <= n; i++) insert(rt[i - 1], rt[i], w[pre[i]], 30);
    while (q--) {
        scanf("%d%d%d", &opt, &a, &b);
        if (opt == 1) printf("%d\n", ask(rt[dfn[a] - 1], rt[ended[a]], b, 30));
        else scanf("%d", &c), printf("%d\n", query(a, b, c));
    }
}