DDP 模板(Top Tree)

#include <bits/stdc++.h>
using i64 = long long;

template<typename Ta, typename Tb>
inline void chkmax(Ta &a, const Tb &b) {if (a < b)  a = b;}
template<typename Ta, typename Tb>
inline void chkmin(Ta &a, const Tb &b) {if (a > b)  a = b;}
constexpr int MEMORY_POOL = 1 << 20;
char BUFFER[MEMORY_POOL], *PS = BUFFER, *PT = BUFFER;
inline char gc() {
    if (PS == PT)   PT = (PS = BUFFER) + fread(BUFFER, 1, MEMORY_POOL, stdin);
    return PS == PT ? EOF : *PS++;
}
template<typename T>
inline void read(T &ans) {
    ans = 0;
    T w = 1;
    char c = gc();
    while (!isdigit(c)) {
        if (c == '-')   w = -1;
        c = gc();
    }
    while (isdigit(c)) {
        ans = (ans << 3) + (ans << 1) + (c ^ 48);
        c = gc();
    }
    ans *= w;
}
template<typename T, typename ...Ts>
void read(T &a, Ts&... other) {
    read(a);
    read(other...);
}

char OUTB[MEMORY_POOL];
char *P = OUTB;
inline void flush() {fwrite(OUTB, 1, P - OUTB, stdout);P = OUTB;}
inline void push(const char &x) {
    if (P == OUTB + MEMORY_POOL)
        flush();
    *P++ = x;
}
inline void write(i64 x) {
    if (x < 0)
        x = -x, push('-');
    static short stk[30], tt = 0;
    do {
        stk[tt++] = x % 10, x /= 10;
    } while (x);
    while (tt)
        push(stk[--tt] + '0');
}

constexpr int N = 1e6 + 10;
constexpr int M = N << 1;
constexpr int inf = 1e9;

template<typename T>
inline void chkmax(T &a, const T &b) {if (a < b)    a = b;}

std::vector<int> G[N];
int n, m;
int w[N];

inline void add(int u, int v) {G[u].push_back(v);}

namespace TopTree {
    struct Cluster {
        int u, v;
        int f[2][2];
        int dis;
        int siz;
    };

    // b rake 到 a 上
    inline Cluster Rake(const Cluster &a, const Cluster &b) {
        Cluster res;
        assert(a.u == b.u);

        res.u = a.u, res.v = a.v;
        res.siz = a.siz + b.siz;
        res.dis = a.dis;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++) {
                res.f[i][j] = std::max(a.f[i][j] + w[b.v] + b.f[i][1], a.f[i][j] + b.f[i][0]);
                chkmax(res.f[i][j], -inf);
            }
        if (res.dis == 1)
            res.f[1][1] = -inf;
        return res;
    }

    // a, b Compress
    inline Cluster Compress(const Cluster &a, const Cluster &b) {
        Cluster res;
        assert(a.v == b.u);

        res.u = a.u, res.v = b.v;
        res.siz = a.siz + b.siz;
        res.dis = a.dis + b.dis;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++) {
                res.f[i][j] = std::max(a.f[i][1] + w[a.v] + b.f[1][j], a.f[i][0] + b.f[0][j]);
                chkmax(res.f[i][j], -inf);
            }
        if (res.dis == 1)
            res.f[1][1] = -inf;
        return res;
    }

    int totN;
    struct node {
        std::array<int, 2> ch;
        Cluster info;
        int fa, dep, type;   // type 0/1/2 分别为 base/rake/compress
        int& operator [](const int &x) {
            return ch[x];
        }
    } tr[M];

    inline void pull(int u) {
        if (tr[u].type == 0)    return ;
        tr[u].info = (tr[u].type == 1 ? Rake : Compress)(tr[tr[u][0]].info, tr[tr[u][1]].info);
    }

    inline int merge(int u, int v, int type) {
        totN++;
        tr[totN][0] = u, tr[totN][1] = v;
        tr[u].fa = totN, tr[v].fa = totN;
        tr[totN].type = type;
        pull(totN);
        return totN;
    }

    int Divide_And_Conquer(std::vector<int> &vec, int l, int r, int type) {
        if (l == r)
            return vec[l];
        int gsum = 0;
        for (int i = l; i <= r; i++)
            gsum += tr[vec[i]].info.siz;

        int cur = 0, mid = r - 1;

        for (int i = l; i <= r - 1; i++) {
            cur += tr[vec[i]].info.siz;
            if (cur * 2 >= gsum) {
                mid = i;
                break;
            }
        }

        int ls = Divide_And_Conquer(vec, l, mid, type);
        int rs = Divide_And_Conquer(vec, mid + 1, r, type);
        return merge(ls, rs, type);
    }


    // 到 (u, fa[u]) 的基簇的 id
    int fa_id[N];
    int Ssiz[N], son[N], fa[N], dep[N];
    void dfs_pre(int u) {
        dep[u] = dep[fa[u]] + 1;
        Ssiz[u] = 1;
        for (const int &v : G[u]) {
            if (v == fa[u])
                continue;
            fa[v] = u;

            Cluster t;
            t.u = u, t.v = v;
            t.f[1][1] = -inf;
            t.dis = 1, t.siz = 1;
            tr[++totN] = {{0, 0}, t, 0, 0, 0};
            fa_id[v] = totN;

            dfs_pre(v);
            Ssiz[u] += Ssiz[v];
            if (Ssiz[v] > Ssiz[son[u]])
                son[u] = v;
        }
    }

    int build(int tp) {
        std::vector<int> seq;
        if (fa_id[tp])
            seq.push_back(fa_id[tp]);

        for (int u = tp; son[u]; u = son[u]) {
            std::vector<int> seq2;
            // 先把轻子树全部合并起来
            for (const int &v : G[u]) {
                if (v == son[u] || v == fa[u])
                    continue;
                seq2.push_back(build(v));
            }

            if (!seq2.empty()) {
                int cur = fa_id[son[u]];
                // 分治 Rake 其他子树，然后 Rake 到重儿子上
                int out = Divide_And_Conquer(seq2, 0, (int)seq2.size() - 1, 1);
                seq.push_back(merge(cur, out, 1));
            } else {
                seq.push_back(fa_id[son[u]]);
            }
        }
        return Divide_And_Conquer(seq, 0, (int)seq.size() - 1, 2);
    }

    int rt;
    void dfs2(int u) {
        tr[u].dep = tr[tr[u].fa].dep + 1;
        if (tr[u].type)
            dfs2(tr[u][0]), dfs2(tr[u][1]);
    }
    void re_update(int u) {
        while (tr[u].fa)
            u = tr[u].fa, pull(u);
    }
    void init(int n) {
        dfs_pre(n);
        rt = build(n);
        dfs2(rt);
    }
};

using namespace TopTree;

int main() {
#ifdef HeratinoNelofus
    freopen("input.txt", "r", stdin);
#endif

    read(n, m);
    for (int i = 1; i <= n; i++)
        read(w[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        read(u, v);
        add(u, v), add(v, u);
    }
    n++;
    add(n, 1), add(1, n);
    TopTree::init(n);
    int lst = 0;
    while (m--) {
        int p, x;
        read(p, x);
        p ^= lst;
        w[p] = x;
        re_update(fa_id[p]);
        auto t = tr[rt].info;
        lst = std::max(t.f[0][1] + w[t.v], t.f[0][0]);
        write(lst);
        push('\n');
    }
    flush();
    return 0;
}