思路题解

关键观察

• 点 $u$ 的权值 $w_u$ 只依赖 $a_u$ 以及 $u$ 的直接子节点的取值集合 ${a_v\mid v\in \mathrm{child}(u)}$。 因而一次把 $a_x$ 改成 $y$ 的修改，至多影响 两个点：$x$ 自身（若 $x$ 有子）与其父亲 $p=\mathrm{fa}(x)$（因为 $w_p$ 里包含$a_p\oplus a_x$ 这一候选）。这不会继续向更高祖先传递（$w_{\mathrm{fa}(mathrm{fa}(x))}$ 不依赖 $w_p$）。

• 区间查询（类型 $2$）是“按编号”的最大值；子树查询（类型 $3$）可以用欧拉序把子树压成一段区间。因此维护两棵最大值线段树即可：

  • 一棵按编号 $1\sim n$；
  • 一棵按欧拉序时间戳 $tin[u]$（子树区间为 $[tin[u], tout[u]]$）。

如何快速维护 $w_u$

对于有子节点的 $u$，有

直接扫子节点要 $O(\deg(u))$，最坏会很大。为兼顾效率与内存，使用度分治（轻重点）：

• 设阈值 $B$（例如 $B=700$）。

• 若 $|\mathrm{child}(u)|\le B$（轻点），每次需要时线性扫全部子节点计算 $w_u$，代价 $O(B)$；

• 若 $|\mathrm{child}(u)|>B$（重点），为该点 $u$ 维护一个可删可插的按位字典树（bitwise trie），存的是它所有子节点的取值集合 ${a_v}$。

  • 查询 $w_u$ 时：在字典树上用关键字 $a_u$ 做“最大异或”查询，$O(30)$；
  • 当某个子 $x$ 的值从旧值变为新值时：在 $u$ 的字典树里删旧插新，$O(30)$。

因为一次修改 $a_x$ 只影响 $x$ 与 $p=\mathrm{fa}(x)$：

• 对 $x$：若 $x$ 有子，重新求 $w_x$（轻点线性扫 / 重点字典树查询；若 $x$ 是叶，则 $w_x=a_x$）；
• 对 $p$：在 $p$ 的数据结构里把 $a_x$ 的旧值删掉、新值插入，再重新求 $w_p$（轻点线性扫 / 重点字典树查询）。

正确性说明

• 定义所需的仅是 $a_u$ 与其子取值；修改 $a_x$ 不会改变任何人的“子集合”结构，且不会影响到孙辈及以上节点的 $w$ 依赖关系。
• 线段树分别覆盖“按编号”和“按欧拉序”的最大值，因此类型 $2$ 与类型 $3$ 的答案都是对应区间的最大 $w$ 值，正确。

复杂度与参数

• 预处理（建树、根为 $1$ 的父子关系、欧拉序）：$O(n)$。
• 对每个重点 $u$，字典树大小与它的子数成正比，插入 $O(30)$。所有重点总存储与边数同阶。
• 每次修改操作的代价为 $O(B + 30 + \log n)$（两次点更新到两棵线段树 + 轻点重算或重点字典树维护）。
• 查询操作（类型 $2/3$）：$O(\log n)$。
• 取 $B\simeq 700$ 可在 $n,m\le 3\times 10^5$ 下取得良好平衡。

C++

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

/*
  思路：
  - 建父子关系（根1），欧拉序 tin/tout；
  - 维护 w[u]：
      叶：w[u] = a[u]
      非叶：轻点扫描子，重点用可删字典树（只存子取值），查询 key=a[u] 的最大异或。
  - 两棵线段树：一棵按编号 [1..n]；一棵按欧拉序 [1..n]。
  - 修改 ax -> y 只影响 x 与 p=fa[x] 两个点的 w 值，同时更新两棵线段树对应位置。
*/

// -------- 线段树（区间最大，点更新）--------
struct SegTree {
    int n;
    vector<int> seg;
    SegTree() {}
    SegTree(int n): n(n), seg(4*n+4, INT_MIN) {}
    void build(const vector<int>& base, int idx, int l, int r) {
        if (l==r) { seg[idx] = base[l]; return; }
        int mid=(l+r)>>1;
        build(base, idx<<1, l, mid);
        build(base, idx<<1|1, mid+1, r);
        seg[idx] = max(seg[idx<<1], seg[idx<<1|1]);
    }
    void build(const vector<int>& base) { build(base,1,1,n); }
    void pointUpdate(int idx, int l, int r, int pos, int val) {
        if (l==r) { seg[idx]=val; return; }
        int mid=(l+r)>>1;
        if (pos<=mid) pointUpdate(idx<<1,l,mid,pos,val);
        else pointUpdate(idx<<1|1,mid+1,r,pos,val);
        seg[idx] = max(seg[idx<<1], seg[idx<<1|1]);
    }
    void pointUpdate(int pos, int val) { pointUpdate(1,1,n,pos,val); }
    int rangeQuery(int idx,int l,int r,int ql,int qr){
        if (ql<=l && r<=qr) return seg[idx];
        int mid=(l+r)>>1; int ans=INT_MIN;
        if (ql<=mid) ans=max(ans, rangeQuery(idx<<1,l,mid,ql,qr));
        if (qr>mid)  ans=max(ans, rangeQuery(idx<<1|1,mid+1,r,ql,qr));
        return ans;
    }
    int rangeQuery(int l,int r){ return rangeQuery(1,1,n,l,r); }
};

// -------- 可删字典树（仅存某点所有子节点的 a 值）--------
struct DelTrie {
    struct Node { int ch[2]; int cnt; Node(){ ch[0]=ch[1]=-1; cnt=0; } };
    vector<Node> t;
    static const int MAXB = 30; // a_i <= 1e9
    DelTrie(){ t.reserve(1); t.push_back(Node()); } // root

    void modify(int x, int delta) {
        int p=0; t[p].cnt += delta;
        for (int b=MAXB-1;b>=0;--b) {
            int bit = (x>>b)&1;
            if (t[p].ch[bit]==-1) {
                if (delta<0) { // 删除路径不存在，理论不该发生
                    // 为稳妥，直接返回
                    return;
                }
                t[p].ch[bit] = (int)t.size();
                t.push_back(Node());
            }
            p = t[p].ch[bit];
            t[p].cnt += delta;
        }
    }
    void insertVal(int x){ modify(x, +1); }
    void eraseVal(int x){ modify(x, -1); }

    int maxXor(int key) const {
        if (t[0].cnt<=0) return INT_MIN; // 空
        int p=0, ans=0;
        for (int b=MAXB-1;b>=0;--b) {
            int kb = (key>>b)&1;
            int want = kb^1; // 想走相反位
            int nxt = t[p].ch[want];
            if (nxt!=-1 && t[nxt].cnt>0) { // 能走想要的
                ans |= (1<<b);
                p = nxt;
            } else { // 否则只能走同位
                nxt = t[p].ch[kb];
                if (nxt==-1 || t[nxt].cnt<=0) {
                    // 理论不会：至少还有一条路径
                    break;
                }
                p = nxt;
            }
        }
        return ans;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if(!(cin>>n>>m)) return 0;
    vector<int> a(n+1);
    for (int i=1;i<=n;i++) cin>>a[i];

    vector<vector<int>> adj(n+1);
    for (int i=0;i<n-1;i++){
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 建父子关系 + 欧拉序（迭代DFS）
    vector<int> fa(n+1,0);
    vector<vector<int>> child(n+1);
    vector<int> tin(n+1), tout(n+1), euler(n+1);
    int timer=0;

    vector<int> it(n+1,0);
    vector<int> st; st.reserve(n);
    st.push_back(1); fa[1]=0;

    // 第一次遍历建立fa与child，并生成一个DFS序用于再做欧拉入出
    // 这里直接做“手写欧拉”：
    vector<int> stackU; stackU.reserve(n);
    vector<int> stackState; stackState.reserve(n);
    stackU.push_back(1); stackState.push_back(0);
    fa[1]=0;
    while(!stackU.empty()){
        int u = stackU.back();
        int state = stackState.back();
        if(state==0){
            tin[u] = ++timer;
            euler[timer]=u;
            stackState.back()=1;
            for(int v: adj[u]){
                if(v==fa[u]) continue;
                fa[v]=u;
                child[u].push_back(v);
                stackU.push_back(v);
                stackState.push_back(0);
            }
        }else{
            tout[u]=timer;
            stackU.pop_back();
            stackState.pop_back();
        }
    }

    // 轻重划分
    const int B = 700;
    vector<char> isHeavy(n+1, 0);
    for (int u=1;u<=n;u++){
        if ((int)child[u].size() > B) isHeavy[u]=1;
    }

    // 为重点建立字典树，并初始化 w[u]
    vector<unique_ptr<DelTrie>> trie(n+1);
    vector<int> w(n+1, INT_MIN);
    for (int u=1;u<=n;u++){
        if (isHeavy[u]) {
            trie[u] = make_unique<DelTrie>();
            trie[u]->t.reserve( (int)child[u].size()*32 + 1 );
            for (int v: child[u]) trie[u]->insertVal(a[v]);
        }
    }
    auto recomputeLight = [&](int u)->int{
        if (child[u].empty()) return a[u];
        int best = INT_MIN;
        for (int v: child[u]) best = max(best, a[u]^a[v]);
        return best;
    };
    for (int u=1;u<=n;u++){
        if (child[u].empty()) w[u]=a[u];
        else if (isHeavy[u]) w[u]=trie[u]->maxXor(a[u]);
        else w[u]=recomputeLight(u);
    }

    // 两棵线段树：编号序与欧拉序
    vector<int> baseId(n+1), baseEuler(n+1);
    for (int u=1;u<=n;u++){
        baseId[u]=w[u];
        baseEuler[tin[u]]=w[u];
    }
    SegTree segId(n), segEuler(n);
    segId.build(baseId);
    segEuler.build(baseEuler);

    // 处理操作
    for (int i=0;i<m;i++){
        int type; cin>>type;
        if (type==1){
            int x,y; cin>>x>>y;
            int old = a[x];
            a[x]=y;

            // 更新 x
            int wx;
            if (child[x].empty()) wx = a[x];
            else if (isHeavy[x]) wx = trie[x]->maxXor(a[x]);
            else wx = recomputeLight(x);
            if (wx!=w[x]){
                w[x]=wx;
                segId.pointUpdate(x, w[x]);
                segEuler.pointUpdate(tin[x], w[x]);
            }

            // 更新父亲 p
            int p = fa[x];
            if (p!=0){
                int wp;
                if (isHeavy[p]){
                    trie[p]->eraseVal(old);
                    trie[p]->insertVal(a[x]);
                    wp = trie[p]->maxXor(a[p]);
                }else{
                    wp = recomputeLight(p);
                }
                if (wp!=w[p]){
                    w[p]=wp;
                    segId.pointUpdate(p, w[p]);
                    segEuler.pointUpdate(tin[p], w[p]);
                }
            }
        }else if (type==2){
            int l,r; cin>>l>>r;
            cout<<segId.rangeQuery(l,r)<<"\n";
        }else{ // type==3
            int x; cin>>x;
            cout<<segEuler.rangeQuery(tin[x], tout[x])<<"\n";
        }
    }
    return 0;
}

Python

import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

# 线段树（区间最大）
class SegTree:
    def __init__(self, n):
        self.n = n
        self.seg = [-(1<<60)] * (4*n + 5)
    def build(self, base, idx, l, r):
        if l == r:
            self.seg[idx] = base[l]
            return
        mid = (l + r) >> 1
        self.build(base, idx<<1, l, mid)
        self.build(base, idx<<1|1, mid+1, r)
        self.seg[idx] = max(self.seg[idx<<1], self.seg[idx<<1|1])
    def point_update(self, idx, l, r, pos, val):
        if l == r:
            self.seg[idx] = val
            return
        mid = (l + r) >> 1
        if pos <= mid:
            self.point_update(idx<<1, l, mid, pos, val)
        else:
            self.point_update(idx<<1|1, mid+1, r, pos, val)
        self.seg[idx] = max(self.seg[idx<<1], self.seg[idx<<1|1])
    def range_query(self, idx, l, r, ql, qr):
        if ql <= l and r <= qr:
            return self.seg[idx]
        mid = (l + r) >> 1
        res = -(1<<60)
        if ql <= mid:
            res = max(res, self.range_query(idx<<1, l, mid, ql, qr))
        if qr > mid:
            res = max(res, self.range_query(idx<<1|1, mid+1, r, ql, qr))
        return res

# 可删字典树（仅存某点的所有子 a 值）
class DelTrie:
    MAXB = 30
    def __init__(self):
        # 每个节点: [ch0, ch1, cnt]
        self.ch0 = [-1]
        self.ch1 = [-1]
        self.cnt = [0]
    def _new(self):
        self.ch0.append(-1)
        self.ch1.append(-1)
        self.cnt.append(0)
        return len(self.cnt) - 1
    def modify(self, x, delta):
        p = 0
        self.cnt[p] += delta
        for b in range(self.MAXB - 1, -1, -1):
            bit = (x >> b) & 1
            if bit == 0:
                if self.ch0[p] == -1:
                    if delta < 0:
                        return
                    self.ch0[p] = self._new()
                p = self.ch0[p]
            else:
                if self.ch1[p] == -1:
                    if delta < 0:
                        return
                    self.ch1[p] = self._new()
                p = self.ch1[p]
            self.cnt[p] += delta
    def insert_val(self, x):
        self.modify(x, +1)
    def erase_val(self, x):
        self.modify(x, -1)
    def max_xor(self, key):
        if self.cnt[0] <= 0:
            return -10**18
        p = 0
        ans = 0
        for b in range(self.MAXB - 1, -1, -1):
            kb = (key >> b) & 1
            want = kb ^ 1
            if want == 1:
                nxt = self.ch1[p]
                if nxt != -1 and self.cnt[nxt] > 0:
                    ans |= (1 << b)
                    p = nxt
                else:
                    nxt = self.ch0[p]
                    if nxt == -1 or self.cnt[nxt] <= 0:
                        break
                    p = nxt
            else:
                nxt = self.ch0[p]
                if nxt != -1 and self.cnt[nxt] > 0:
                    p = nxt
                else:
                    nxt = self.ch1[p]
                    if nxt == -1 or self.cnt[nxt] <= 0:
                        break
                    ans |= (1 << b)
                    p = nxt
        return ans

def main():
    n, m = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    adj = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)

    # 建父子 + 欧拉序（迭代）
    fa = [0]*(n+1)
    child = [[] for _ in range(n+1)]
    tin = [0]*(n+1)
    tout = [0]*(n+1)
    timer = 0
    stackU = [1]
    stackSt = [0]
    fa[1] = 0
    while stackU:
        u = stackU[-1]
        st = stackSt[-1]
        if st == 0:
            timer += 1
            tin[u] = timer
            stackSt[-1] = 1
            for v in adj[u]:
                if v == fa[u]:
                    continue
                fa[v] = u
                child[u].append(v)
                stackU.append(v)
                stackSt.append(0)
        else:
            tout[u] = timer
            stackU.pop()
            stackSt.pop()

    B = 700
    isHeavy = [False]*(n+1)
    for u in range(1, n+1):
        if len(child[u]) > B:
            isHeavy[u] = True

    trie = [None]*(n+1)
    for u in range(1, n+1):
        if isHeavy[u]:
            t = DelTrie()
            # 预留无法直接做，这里直接插
            for v in child[u]:
                t.insert_val(a[v])
            trie[u] = t

    def recompute_light(u):
        if not child[u]:
            return a[u]
        best = -10**18
        au = a[u]
        for v in child[u]:
            val = au ^ a[v]
            if val > best:
                best = val
        return best

    w = [-(1<<60)]*(n+1)
    for u in range(1, n+1):
        if not child[u]:
            w[u] = a[u]
        elif isHeavy[u]:
            w[u] = trie[u].max_xor(a[u])
        else:
            w[u] = recompute_light(u)

    baseId = [0]*(n+1)
    baseEuler = [0]*(n+1)
    for u in range(1, n+1):
        baseId[u] = w[u]
        baseEuler[tin[u]] = w[u]

    segId = SegTree(n)
    segId.build(baseId, 1, 1, n)
    segEuler = SegTree(n)
    segEuler.build(baseEuler, 1, 1, n)

    out = []
    for _ in range(m):
        op = input().split()
        t = int(op[0])
        if t == 1:
            x = int(op[1]); y = int(op[2])
            old = a[x]
            a[x] = y
            # 更新 x
            if not child[x]:
                wx = a[x]
            elif isHeavy[x]:
                wx = trie[x].max_xor(a[x])
            else:
                wx = recompute_light(x)
            if wx != w[x]:
                w[x] = wx
                segId.point_update(1, 1, n, x, w[x])
                segEuler.point_update(1, 1, n, tin[x], w[x])
            # 更新父亲
            p = fa[x]
            if p != 0:
                if isHeavy[p]:
                    trie[p].erase_val(old)
                    trie[p].insert_val(a[x])
                    wp = trie[p].max_xor(a[p])
                else:
                    wp = recompute_light(p)
                if wp != w[p]:
                    w[p] = wp
                    segId.point_update(1, 1, n, p, w[p])
                    segEuler.point_update(1, 1, n, tin[p], w[p])
        elif t == 2:
            l = int(op[1]); r = int(op[2])
            out.append(str(segId.range_query(1, 1, n, l, r)))
        else:
            x = int(op[1])
            out.append(str(segEuler.range_query(1, 1, n, tin[x], tout[x])))

    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

/*
  与 C++ 版本相同的思路：
  - 轻重划分：重点用可删字典树（仅存子 a 值），轻点线性扫
  - 两棵线段树：编号序与欧拉序
*/

public class Main {
    static class FastScanner {
        BufferedInputStream in;
        byte[] buffer = new byte[1 << 16];
        int ptr = 0, len = 0;
        FastScanner(InputStream is){ in = new BufferedInputStream(is); }
        int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') {
                x = x*10 + c - '0';
                c = read();
            }
            return x * sgn;
        }
    }

    // 线段树（最大值）
    static class SegTree {
        int n;
        int[] seg;
        SegTree(int n){ this.n=n; seg = new int[4*n+5]; Arrays.fill(seg, Integer.MIN_VALUE); }
        void build(int[] base, int idx, int l, int r){
            if (l==r){ seg[idx]=base[l]; return; }
            int mid=(l+r)>>1;
            build(base, idx<<1, l, mid);
            build(base, idx<<1|1, mid+1, r);
            seg[idx]=Math.max(seg[idx<<1], seg[idx<<1|1]);
        }
        void pointUpdate(int idx,int l,int r,int pos,int val){
            if (l==r){ seg[idx]=val; return; }
            int mid=(l+r)>>1;
            if (pos<=mid) pointUpdate(idx<<1,l,mid,pos,val);
            else pointUpdate(idx<<1|1,mid+1,r,pos,val);
            seg[idx]=Math.max(seg[idx<<1], seg[idx<<1|1]);
        }
        int rangeQuery(int idx,int l,int r,int ql,int qr){
            if (ql<=l && r<=qr) return seg[idx];
            int mid=(l+r)>>1, ans=Integer.MIN_VALUE;
            if (ql<=mid) ans=Math.max(ans, rangeQuery(idx<<1,l,mid,ql,qr));
            if (qr>mid)  ans=Math.max(ans, rangeQuery(idx<<1|1,mid+1,r,ql,qr));
            return ans;
        }
    }

    // 可删字典树（仅存某点全部子 a 值）
    static class DelTrie {
        static final int MAXB = 30;
        ArrayList<int[]> nodes; // [ch0, ch1, cnt]
        DelTrie(){
            nodes = new ArrayList<>();
            nodes.add(new int[]{-1,-1,0}); // root
        }
        int newNode(){
            nodes.add(new int[]{-1,-1,0});
            return nodes.size()-1;
        }
        void modify(int x, int delta){
            int p=0;
            nodes.get(p)[2] += delta;
            for (int b=MAXB-1;b>=0;--b){
                int bit = (x>>b)&1;
                int[] cur = nodes.get(p);
                if (bit==0){
                    if (cur[0]==-1){
                        if (delta<0) return; // 安全处理
                        cur[0]=newNode();
                    }
                    p = cur[0];
                }else{
                    if (cur[1]==-1){
                        if (delta<0) return;
                        cur[1]=newNode();
                    }
                    p = cur[1];
                }
                nodes.get(p)[2] += delta;
            }
        }
        void insertVal(int x){ modify(x, +1); }
        void eraseVal(int x){ modify(x, -1); }
        int maxXor(int key){
            if (nodes.get(0)[2]<=0) return Integer.MIN_VALUE;
            int p=0, ans=0;
            for (int b=MAXB-1;b>=0;--b){
                int kb=(key>>b)&1;
                int want=kb^1;
                int[] cur = nodes.get(p);
                if (want==1){
                    int nxt = cur[1];
                    if (nxt!=-1 && nodes.get(nxt)[2]>0){
                        ans |= (1<<b);
                        p = nxt;
                    }else{
                        nxt = cur[0];
                        if (nxt==-1 || nodes.get(nxt)[2]<=0) break;
                        p = nxt;
                    }
                }else{
                    int nxt = cur[0];
                    if (nxt!=-1 && nodes.get(nxt)[2]>0){
                        p = nxt;
                    }else{
                        nxt = cur[1];
                        if (nxt==-1 || nodes.get(nxt)[2]<=0) break;
                        ans |= (1<<b);
                        p = nxt;
                    }
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int m = fs.nextInt();
        int[] a = new int[n+1];
        for (int i=1;i<=n;i++) a[i]=fs.nextInt();
        ArrayList<Integer>[] adj = new ArrayList[n+1];
        for (int i=1;i<=n;i++) adj[i]=new ArrayList<>();
        for (int i=0;i<n-1;i++){
            int u=fs.nextInt(), v=fs.nextInt();
            adj[u].add(v); adj[v].add(u);
        }

        int[] fa = new int[n+1];
        ArrayList<Integer>[] child = new ArrayList[n+1];
        for (int i=1;i<=n;i++) child[i]=new ArrayList<>();
        int[] tin = new int[n+1], tout = new int[n+1];
        int timer=0;

        // 迭代 DFS + 欧拉序
        int[] stackU = new int[n];
        int[] stackSt = new int[n];
        int top=0; stackU[top]=1; stackSt[top]=0; fa[1]=0;
        while (top>=0){
            int u=stackU[top], st=stackSt[top];
            if (st==0){
                tin[u]=++timer;
                stackSt[top]=1;
                for (int v: adj[u]){
                    if (v==fa[u]) continue;
                    fa[v]=u;
                    child[u].add(v);
                    ++top; stackU[top]=v; stackSt[top]=0;
                }
            }else{
                tout[u]=timer;
                --top;
            }
        }

        final int B = 700;
        boolean[] isHeavy = new boolean[n+1];
        for (int u=1;u<=n;u++){
            if (child[u].size()>B) isHeavy[u]=true;
        }

        DelTrie[] trie = new DelTrie[n+1];
        for (int u=1;u<=n;u++){
            if (isHeavy[u]){
                trie[u]=new DelTrie();
                for (int v: child[u]) trie[u].insertVal(a[v]);
            }
        }

        // 轻点重算
        java.util.function.IntUnaryOperator recomputeLight = (u)->{
            if (child[u].isEmpty()) return a[u];
            int best = Integer.MIN_VALUE;
            int au = a[u];
            for (int v: child[u]) best = Math.max(best, au ^ a[v]);
            return best;
        };

        int[] w = new int[n+1];
        for (int u=1;u<=n;u++){
            if (child[u].isEmpty()) w[u]=a[u];
            else if (isHeavy[u]) w[u]=trie[u].maxXor(a[u]);
            else w[u]=recomputeLight.applyAsInt(u);
        }

        int[] baseId = new int[n+1];
        int[] baseEuler = new int[n+1];
        for (int u=1;u<=n;u++){
            baseId[u]=w[u];
            baseEuler[tin[u]]=w[u];
        }
        SegTree segId = new SegTree(n);
        segId.build(baseId,1,1,n);
        SegTree segEuler = new SegTree(n);
        segEuler.build(baseEuler,1,1,n);

        StringBuilder out = new StringBuilder();
        for (int i=0;i<m;i++){
            int type = fs.nextInt();
            if (type==1){
                int x=fs.nextInt(), y=fs.nextInt();
                int old=a[x];
                a[x]=y;

                int wx;
                if (child[x].isEmpty()) wx=a[x];
                else if (isHeavy[x]) wx=trie[x].maxXor(a[x]);
                else wx=recomputeLight.applyAsInt(x);
                if (wx!=w[x]){
                    w[x]=wx;
                    segId.pointUpdate(1,1,n,x,w[x]);
                    segEuler.pointUpdate(1,1,n,tin[x],w[x]);
                }

                int p=fa[x];
                if (p!=0){
                    int wp;
                    if (isHeavy[p]){
                        trie[p].eraseVal(old);
                        trie[p].insertVal(a[x]);
                        wp=trie[p].maxXor(a[p]);
                    }else{
                        wp=recomputeLight.applyAsInt(p);
                    }
                    if (wp!=w[p]){
                        w[p]=wp;
                        segId.pointUpdate(1,1,n,p,w[p]);
                        segEuler.pointUpdate(1,1,n,tin[p],w[p]);
                    }
                }
            }else if (type==2){
                int l=fs.nextInt(), r=fs.nextInt();
                out.append(segId.rangeQuery(1,1,n,l,r)).append('\n');
            }else{
                int x=fs.nextInt();
                out.append(segEuler.rangeQuery(1,1,n,tin[x],tout[x])).append('\n');
            }
        }
        System.out.print(out.toString());
    }
}

题目内容

小美有一棵 $n$ 个节点(编号为 $1$ ~ $n$)、由 $n-1$ 条边构成的无向树，根节点为 $1$ 。每个节点 $i$ 有一个值 $a_i$ 。对于任意节点 $u$ ，其权值定义如下：

• 如果 $u$ 有子节点，则权值为该节点与所有子节点值的按位异或的最大值，即

• 如果 $u$ 是叶子节点，则权值为 $a_u$。

接下来小美会对这棵树进行 $m$ 次操作，每次操作从以下三种类型中选择一种执行：

• 类型 $1$ $x$ $y$： 将节点 $x$ 的值 $a_x$ 修改为 $y$ ，

• 类型 $2$ $x$ $y$ ：查询当前所有编号在区间 $[l,r]$ 内的节点的最大权值，$(1≦x≦y≦n)$ ;

• 类型 $3$ $x$ ：查询以节点 $x$ 为根的子树中所有节点的最大权值，$(1 ≦x≦n)$ 。

输入描述

第一行输入两个整数 $n,m(1≦n,m ≦3×10^5)$ ，分别表示节点数和操作次数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦a_i≦ 10^9)$ ，表示初始时每个节点的值。

接下来 $n-1$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i(1 ≦ u_i, v_i ≦ n; u_i≠v_i)$ ，表示树上第 $i$ 条树边。

随后 $m$ 行，每行对应一次操作，格式如题目描述所示。

输出描述

对于每个查询操作(类型 $2$ 或 $3$ )，输出一行，表示查询结果(最大权值)。

样例1

输入

3 4
1 2 3
1 2
1 3
2 2 3
3 1
1 1 5
3 1

输出

3 
3 
7

样例2

输入

1 2
10
2 1 1
3 1

输出

10
10