代码

/**********************************************************
 * By Jerry Zheng
 * 
 * Get more points as possible.
 * Is the understanding of the statement correct?
 * If Subtask #2 is too hard, why not try Subtask #3?
 * 
 * Think twice, code once.
 * Are there any counterexamples to your algo?
 * Is the sol too heavy to debug?
 * Is the Time & Meomry complexity correct?
 * 
 * DON'T MAKE STUPID MISTAKES!!!!!
 * file-IO? DEBUG output? array size?
 * boundaries? long long?
 *
                         _ooOoo_
                        o8888888o
                        88" . "88
                        (| -_- |)
                        O\  =  /O
                     ____/`---'\____
                   .'  \|     |//  `.
                  /  \|||  :  |||//  \
                 /  _||||| -:- |||||-  \
                 |   | \\  -  /// |   |
                 | \_|  ''\---/''  |   |
                 \  .-\__  `-`  ___/-. /
               ___`. .'  /--.--\  `. . __
            ."" '<  `.___\_<|>_/___.'  >'"".
           | | :  `- \`.;`\ _ /`;.`/ - ` : | |
           \  \ `-.   \_ __\ /__ _/   .-` /  /
      ======`-.____`-.___\_____/___.-`____.-'======
                         `=---='
      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                 佛祖保佑        永无BUG
**********************************************************/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define IL inline
#define CT const
#define RG register
#define TT template <typename Ty>

namespace io {
const int MaxBuff = 1 << 15, MaxOut = 1 << 24;
char b[MaxBuff], *S = b, *T = b, buff[MaxOut], *iter = buff;
FILE *_IN = stdin, *_OUT = stdout;
IL char gc() { return S == T && (T = (S = b) + fread(b, 1, MaxBuff, _IN), S == T) ? 0 : *S++; }
IL void ps(const char *s) { while (*s) *iter++ = *s++; }
IL void pc(const char s) { *iter++ = s; }
IL void fflush() { fwrite(buff, 1, iter - buff, _OUT), iter = buff, fclose(_IN), fclose(_OUT); }
} // namespace io

TT IL Ty max(CT Ty& a, CT Ty& b) { return a > b ? a : b; }
TT IL Ty min(CT Ty& a, CT Ty& b) { return a < b ? a : b; }
TT IL void cmax(Ty& a, CT Ty& b) { if (b > a) a = b; }
TT IL void cmin(Ty& a, CT Ty& b) { if (b < a) a = b; }
TT IL void swap(Ty& a, Ty& b) { Ty t = a; a = b; b = t; }
TT IL void swap(Ty*& a, Ty*& b) { Ty *t = a; a = b; b = t; }

TT IL void read(Ty& t) {
    t = 0; int f = 1; RG char ch = io::gc();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = io::gc(); }
    do { t = t * 10 + ch - '0'; ch = io::gc(); } while (ch >= '0' && ch <= '9'); t *= f;
}

TT IL void write(Ty x) {
    if (x < 0) io::pc('-');
    if (x > 9) write(x / 10);
    io::pc(x % 10 + '0');
}

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() {
    //io::_IN = fopen("defense.in", "r");
    //io::_OUT= fopen("defense.out", "w");
    read(n), read(m);
    for (char ch = io::gc(); ch != '\n'; ch = io::gc()) ;
    for (int i = 1; i <= n; ++i) read(p[i]);
    for (int i = 1, u, v; i < n; ++i) {
        read(u), read(v);
        addedge(u, v);
    }
    //puts("Input OK!");
    dfs1(1, 0);
    dfs2(1, 1);
    //puts("Dfs OK!");
    for (int i = 0; i < m; ++i) {
        //printf("Starting %d...\n", i);
        int a, x, b, y;
        read(a), read(x), read(b), read(y);
        if (dep[a] < dep[b])
            swap(a, b), swap(x, y);
        if (anc[a] == b && y == 0 && x == 0) {
            io::ps("-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;
        write(ans), io::pc('\n');
        solve(a, x ? inf : -inf);
        solve(b, y ? inf : -inf);
        //printf("%d Done.\n", i);
    }
    io::fflush();
    return 0;
}

评测结果