代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005

const long long INF = 1e18;

namespace matrix_ddp {
    struct matrix {
        long long val[2][2];
        matrix() { val[0][0] = val[0][1] = val[1][0] = val[1][1] = INF; }
        inline matrix operator *(const matrix &x) const {
            matrix ans;
            for (int i = 0; i < 2; ++i)
                for (int j = 0; j < 2; ++j)
                    for (int k = 0; k < 2; ++k)
                        ans.val[i][j] = std::min(ans.val[i][j], val[i][k] + x.val[k][j]);
            return ans;
        }
    };
}

using namespace matrix_ddp;

template<class T> struct segtree {
    T *val;
    T a[N << 2];
    
    #define lson x << 1
    #define rson x << 1 | 1

    inline void set(T *a) { val = a; }
    inline void pushup(int x) { a[x] = a[lson] * a[rson]; }
    inline void build(int x, int l, int r) {
        if (l == r) {
            a[x] = val[l];
            return;
        }
        int mid = l + r >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        pushup(x);
    }
    inline void update(int x, int l, int r, int p) {
        if (l == r) {
            a[x] = val[p];
            return;
        }
        int mid = l + r >> 1;
        if (p <= mid) update(lson, l, mid, p);
        else update(rson, mid + 1, r, p);
        pushup(x);
    }
    inline T query(int x, int l, int r, int L, int R) {
        if (l >= L && r <= R) return a[x];
        int mid = l + r >> 1;
        if (R <= mid) return query(lson, l, mid, L, R);
        if (L > mid) return query(rson, mid + 1, r, L, R);
        return query(lson, l, mid, L, R) * query(rson, mid + 1, r, L, R);
    }
};

segtree<matrix> tree;

long long a[N];
long long f[N][2];
matrix g[N];

int cnt;
int u[N << 1], v[N << 1], h[N];

inline void add(int x, int y) {
    u[++cnt] = h[x];
    v[h[x] = cnt] = y;
}

int num;
int F[N], sz[N], hs[N], top[N], btm[N], id[N];

void dfs1(int x, int fa) {
    F[x] = fa;
    sz[x] = 1;
    int max = 0;
    f[x][1] = a[x];
    for (int i = h[x]; i; i = u[i]) {
        if (v[i] == fa) continue;
        dfs1(v[i], x);
        sz[x] += sz[v[i]];
        if (sz[v[i]] > max) {
            max = sz[v[i]];
            hs[x] = v[i];
        }
        f[x][1] += std::min(f[v[i]][1], f[v[i]][0]);
        f[x][0] += f[v[i]][1];
    }
}

void dfs2(int x, int t) {
    top[x] = t;
    id[x] = ++num;
    btm[t] = x;
    g[id[x]].val[1][1] = a[x];
    g[id[x]].val[0][1] = 0;
    g[id[x]].val[0][0] = INF;
    if (!hs[x]) return;
    dfs2(hs[x], t);
    for (int i = h[x]; i; i = u[i]) {
        if (v[i] == F[x] || v[i] == hs[x]) continue;
        dfs2(v[i], v[i]);
        g[id[x]].val[1][1] += std::min(f[v[i]][1], f[v[i]][0]);
        g[id[x]].val[0][1] += f[v[i]][1];
    }
    g[id[x]].val[1][0] = g[id[x]].val[1][1];
}

int n, m;

inline void update(int x, long long v) {
    g[id[x]].val[1][1] += v - a[x];
    g[id[x]].val[1][0] = g[id[x]].val[1][1];
    a[x] = v;
    while (x) {
        matrix last = tree.query(1, 1, n, id[top[x]], id[btm[top[x]]]);
        tree.update(1, 1, n, id[x]);
        matrix now = tree.query(1, 1, n, id[top[x]], id[btm[top[x]]]);
        x = F[top[x]];
        g[id[x]].val[1][1] += std::min(now.val[1][1], now.val[0][1]) - std::min(last.val[1][1], last.val[0][1]);
        g[id[x]].val[0][1] += now.val[1][1] - last.val[1][1];
        g[id[x]].val[1][0] = g[id[x]].val[1][1];
    }
}

char type[5];

int main() {
    scanf("%d%d%s", &n, &m, &type);
    for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
    for (int i = 1, x, y; i < n; ++i) {
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    tree.set(g);
    tree.build(1, 1, n);
    for (int i = 0, A, x, B, y; i < m; ++i) {
        scanf("%d%d%d%d", &A, &x, &B, &y);
        if (!x && !y && (A == F[B] || B == F[A])) { puts("-1"); continue; }
        int va = a[A], vb = a[B];
        update(A, x ? va - INF : INF);
        update(B, y ? vb - INF : INF);
        matrix ans = tree.query(1, 1, n, 1, id[btm[1]]);
        printf("%lld\n", std::min(ans.val[1][1], ans.val[0][1]) + (x + y) * INF);
        update(A, va);
        update(B, vb);
    }
    return 0;
}

评测结果