代码

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

typedef long long ll;
const int N = 100005;
const ll inf = 1e13; // 这里inf不能太大 谨防爆ll

struct matrix { //矩阵
    ll a[2][2];
    inline friend matrix operator*(const matrix &a, const matrix &b) {
        matrix c;
        c.a[0][0] = min(a.a[0][0] + b.a[0][0],
                        a.a[0][1] + b.a[1][0]); //常数优化,一个个写
        c.a[0][1] = min(a.a[0][0] + b.a[0][1], a.a[0][1] + b.a[1][1]);
        c.a[1][0] = min(a.a[1][0] + b.a[0][0], a.a[1][1] + b.a[1][0]);
        c.a[1][1] = min(a.a[1][0] + b.a[0][1], a.a[1][1] + b.a[1][1]);
        return c;
    }
} val[N];

int n, m, head[N], to[N * 2], nxt[N * 2], tot; //邻接表
int anc[N], dep[N], son[N], siz[N];            //树的基本特征
int seg[N], rev[N], scnt, top[N], tail[N];     // rev:反差表,tail:链尾
ll dp[N][2], p[N];                             //一定一定一定开ll

struct segnode {
    segnode *lc, *rc;
    int l, r;
    matrix g;
    inline void pushup() { g = lc->g * rc->g; }
    segnode(int L, int R) {
        lc = rc = NULL;
        l = L, r = R;
        if (l == r) {
            int u = rev[l];
            g.a[0][0] = 1e18;
            g.a[0][1] = dp[u][0] - dp[son[u]][1];
            g.a[1][1] = g.a[1][0] =
                dp[u][1] - min(dp[son[u]][0], dp[son[u]][1]);
            val[u] = g;
        } else {
            int mid = l + r >> 1;
            lc = new segnode(l, mid);
            rc = new segnode(mid + 1, r);
            pushup();
        }
    }
    void modify(int x) {
        if (l == r && r == x)
            return (void)(g = val[rev[x]]);
        int mid = (l + r) >> 1;
        if (x <= mid)
            lc->modify(x);
        else
            rc->modify(x);
        pushup();
    }
    matrix query(int x, int y) {
        if (x <= l && r <= y)
            return g;
        int mid = l + r >> 1;
        if (y <= mid)
            return lc->query(x, y);
        if (x > mid)
            return rc->query(x, y);
        return lc->query(x, y) * rc->query(x, y);
    }
} * tv[N];

inline void addedge(int x, int y) { //领接表
    nxt[++tot] = head[x], head[x] = tot, to[tot] = y;
    nxt[++tot] = head[y], head[y] = tot, to[tot] = x;
}

void dfs1(int u, int fa) { //树剖dfs1,顺便求树上dp
    anc[u] = fa, dep[u] = dep[fa] + 1, son[u] = 0, siz[u] = 1;
    dp[u][0] = 0, dp[u][1] = p[u];
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa)
            continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]])
            son[u] = v;
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}

void dfs2(int u, int tp) { //树剖dfs2
    top[u] = tp, seg[u] = ++scnt, rev[scnt] = u;
    if (son[u] != 0)
        dfs2(son[u], tp);
    else
        tv[tp] = new segnode(seg[tp], scnt);
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == anc[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
}

void solve(int u, ll x) { //这里x是delta
    p[u] += x;            // p更改
    val[u].a[1][0] += x;  //对val进行相应更改
    val[u].a[1][1] += x;  //勿忘seg
    while (u) {           //树剖惯用写法
        segnode *k = tv[top[u]];
        matrix old = k->query(k->l, k->r); //询问旧
        k->modify(seg[u]);                 //更改
        matrix nw = k->query(k->l, k->r);  //询问新
        u = anc[top[u]];                   // u往上跳
        if (!u)
            break; //到0就结束
        ll oldf, newf;
        oldf = min(old.a[1][1], old.a[1][0]); //传递给祖先
        newf = min(nw.a[1][1], nw.a[1][0]);
        val[u].a[0][1] += newf - oldf;
        oldf = min(oldf, min(old.a[0][0], old.a[0][1]));
        newf = min(newf, min(nw.a[0][0], nw.a[0][1]));
        val[u].a[1][0] += newf - oldf;
        val[u].a[1][1] += newf - oldf;
    }
}

int main() {
    // freopen("defense.in","r",stdin);
    // freopen("defense.out","w",stdout);
    char sos[8]; // sos
    scanf("%d%d%s", &n, &m, sos);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &p[i]);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        addedge(u, v);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 0; i < m; ++i) {
        int a, x, b, y;
        scanf("%d%d%d%d", &a, &x, &b, &y);
        if (dep[a] < dep[b])
            swap(a, b), swap(x, y);
        if (anc[a] == b && y == 0 && x == 0) {
            printf("-1\n");
            continue;
        }
        solve(a, x ? -inf : inf);
        solve(b, y ? -inf : inf);
        matrix temp = tv[1]->query(tv[1]->l, tv[1]->r);
        ll ans = min(min(temp.a[0][0], temp.a[0][1]),
                     min(temp.a[1][1], temp.a[1][0]));
        if (x)
            ans += inf;
        if (y)
            ans += inf;
        printf("%lld\n", ans);
        solve(a, x ? inf : -inf);
        solve(b, y ? inf : -inf);
    }
    return 0;
}

评测结果