代码

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cassert>
#define int long long

const int MAXN = 1e5 + 10, MAXM = 1e5 + 10, INF = 2e9;

int n, m, sum, alarm, cnt;
int a[MAXN], head[MAXN], sz[MAXN], fa[MAXN], son[MAXN], dep[MAXN], dfn[MAXN], bel[MAXN], top[MAXN], est[MAXN];
int ldp[MAXN][2], dp[MAXN][2];

struct Edge {
    int link, to;
} edge[MAXN << 1];

struct Matrix {
    int data[2][2];
    Matrix() {
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                data[i][j] = -INF;
    }
    inline int *operator[] (int x) {
        return data[x];
    }
    inline void fill(int val) {
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                data[i][j] = val;
        return;
    }
    friend inline Matrix operator* (Matrix A, Matrix B) {
        Matrix C;
        for (int i = 0; i < 2; ++i)
            for (int k = 0; k < 2; ++k)
                for (int j = 0; j < 2; ++j)
                    C[i][j] = std::max(C[i][j], A[i][k] + B[k][j]);
        return C;
    }
};
Matrix val[MAXN];

inline Matrix Wi(int a, int b, int c, int d) {
    Matrix A;
    A[0][0] = a, A[0][1] = b, A[1][0] = c, A[1][1] = d;
    return A;
}

template <int N>
struct SegmentTree {
    static const int M = N << 2;
    Matrix data[M];
    #define lc ((x) << 1)
    #define rc ((x) << 1 | 1)
    void build(int x, int L, int R) {
        if (L == R) {
            int u = bel[L];
            data[x] = val[u] = Wi(ldp[u][0], ldp[u][0], ldp[u][1], -INF);
            return;
        }
        int mid = L + R >> 1;
        build(lc, L, mid), build(rc, mid + 1, R), data[x] = data[lc] * data[rc];
        return;
    }
    void update(int x, int L, int R, int pos) {
        if (L == R) return (void) (data[x] = val[bel[pos]]);
        int mid = L + R >> 1;
        pos <= mid ? update(lc, L, mid, pos) : update(rc, mid + 1, R, pos);
        data[x] = data[lc] * data[rc];
        return;
    }
    Matrix query(int x, int L, int R, int ql, int qr) {
        if (L >= ql && R <= qr) return data[x];
        int mid = L + R >> 1;
        if (ql > mid) return query(rc, mid + 1, R, ql, qr);
        else if (qr <= mid) return query(lc, L, mid, ql, qr);
        else return query(lc, L, mid, ql, qr) * query(rc, mid + 1, R, ql, qr);
    }
    #undef lc
    #undef rc
};
SegmentTree <MAXN> T;

inline void add(int u, int v) {
    edge[++sum] = (Edge) { v, head[u] }, head[u] = sum;
    return;
}

void dfs1(int u, int fafa) {
    dep[u] = dep[fafa] + 1, sz[u] = 1, fa[u] = fafa;
    for (int i = head[u]; i; i = edge[i].to) {
        int v = edge[i].link;
        if (v == fafa) continue;
        dfs1(v, u), sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
    return;
}

void dfs2(int u, int tp) {
    dfn[u] = est[tp] = ++alarm, bel[alarm] = u, top[u] = tp;
    if (!son[u]) return; dfs2(son[u], tp);
    for (int i = head[u]; i; i = edge[i].to) {
        int v = edge[i].link;
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
    return;
}

void dfs3(int u) {
    for (int i = head[u]; i; i = edge[i].to) {
        int v = edge[i].link;
        if (v == fa[u] || v == son[u]) continue;
        dfs3(v);
        ldp[u][0] += std::max(dp[v][0], dp[v][1]), ldp[u][1] += dp[v][0];
    }
    dp[u][0] += ldp[u][0], dp[u][1] += ldp[u][1];
    if (!son[u]) return;
    dfs3(son[u]);
    dp[u][0] += std::max(dp[son[u]][0], dp[son[u]][1]), dp[u][1] += dp[son[u]][0];
    return;
}

inline void change(int u, int w) {
    val[u][1][0] += w, a[u] += w;
    while (u) {
        int now = top[u];
        Matrix lst = T.query(1, 1, n, dfn[now], est[now]);
        T.update(1, 1, n, dfn[u]);
        Matrix nxt = T.query(1, 1, n, dfn[now], est[now]);
        u = fa[now];
        val[u][0][0] += std::max(nxt[0][0], nxt[1][0]) - std::max(lst[0][0], lst[1][0]);
        val[u][0][1] = val[u][0][0];
        val[u][1][0] += nxt[0][0] - lst[0][0];
    }
    return;
}

inline int query() {
    Matrix ans = T.query(1, 1, n, dfn[1], est[1]);
    return std::max(ans[0][0], ans[1][0]);
}

signed main() {
    scanf("%lld%lld%*s", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), ldp[i][1] = a[i], cnt += a[i];
    for (int i = 1, u, v; i < n; ++i) scanf("%lld%lld", &u, &v), add(u, v), add(v, u);
    dfs1(1, 0), dfs2(1, 1), dfs3(1), T.build(1, 1, n);
    for (int a, b, x, y; m--;) {
        scanf("%lld%lld%lld%lld", &a, &x, &b, &y);
        if ((fa[a] == b || fa[b] == a) && !x && !y) {
            puts("-1");
            continue;
        }
        change(a, x ? -INF : INF), change(b, y ? -INF : INF);
        printf("%lld\n", cnt - query() + (x ? 0 : INF) + (y ? 0 : INF));
        change(a, x ? INF : -INF), change(b, y ? INF : -INF);
    }
    return 0;
}

评测结果