代码

// This code is AI-generated. (AI 生成的代码)
// NOIP2018 保卫王国: minimum-weight vertex cover with two forced vertices per
// query.  Dynamic tree DP: each node carries a (min,+) matrix built from its
// light children's DP; heavy chains are products of these matrices kept in a
// segment tree.  A query rewrites the two constrained leaves, then recomputes
// the affected chains from the deepest one upward and reads the root chain.
#include <sys/auxv.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
typedef long long ll;
typedef unsigned long long u64;

struct DuckInfo {
    u64 abi_version;
    const char *stdin_ptr; u64 stdin_size;
    char *stdout_ptr; u64 stdout_limit; u64 stdout_size;
    char *stderr_ptr; u64 stderr_limit; u64 stderr_size;
    const char *IB_ptr; u64 IB_limit;
    char *OB_ptr; u64 OB_limit;
    u64 tsc_frequency;
} __attribute__((packed));

enum { MAXN = 100005 };
static const ll INF = (ll)1e12;

int n, m;
ll p[MAXN];
int head[MAXN], nxt[2 * MAXN], to[2 * MAXN], ec;
static inline void ae(int u, int v) { to[++ec] = v; nxt[ec] = head[u]; head[u] = ec; }

int par_[MAXN], dep_[MAXN], sz_[MAXN], heavy_[MAXN], ord_[MAXN];
int top_[MAXN], dfn_[MAXN], rdfn_[MAXN], chain_end_[MAXN], timer;
ll g0[MAXN], g1[MAXN], dp0[MAXN], dp1[MAXN];
signed char cons_[MAXN];

struct Mat { ll a00, a01, a10, a11; };
static inline Mat mul(const Mat &x, const Mat &y) {
    Mat z;
    z.a00 = x.a00 + y.a00 < x.a01 + y.a10 ? x.a00 + y.a00 : x.a01 + y.a10;
    z.a01 = x.a00 + y.a01 < x.a01 + y.a11 ? x.a00 + y.a01 : x.a01 + y.a11;
    z.a10 = x.a10 + y.a00 < x.a11 + y.a10 ? x.a10 + y.a00 : x.a11 + y.a10;
    z.a11 = x.a10 + y.a01 < x.a11 + y.a11 ? x.a10 + y.a01 : x.a11 + y.a11;
    return z;
}
static Mat seg[4 * MAXN];
static inline Mat makeMat(int u) {
    Mat z;
    z.a00 = INF;
    z.a01 = g0[u];
    z.a10 = g1[u];
    z.a11 = g1[u];
    if (cons_[u] == 1) { z.a00 = INF; z.a01 = INF; }
    else if (cons_[u] == 0) { z.a10 = INF; z.a11 = INF; }
    return z;
}
static void build(int node, int l, int r) {
    if (l == r) { seg[node] = makeMat(rdfn_[l]); return; }
    int mid = (l + r) >> 1;
    build(node << 1, l, mid);
    build(node << 1 | 1, mid + 1, r);
    seg[node] = mul(seg[node << 1], seg[node << 1 | 1]);
}
static void upd(int node, int l, int r, int pos, const Mat &M) {
    if (l == r) { seg[node] = M; return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) upd(node << 1, l, mid, pos, M); else upd(node << 1 | 1, mid + 1, r, pos, M);
    seg[node] = mul(seg[node << 1], seg[node << 1 | 1]);
}
static Mat qry(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return seg[node];
    int mid = (l + r) >> 1;
    if (qr <= mid) return qry(node << 1, l, mid, ql, qr);
    if (ql > mid) return qry(node << 1 | 1, mid + 1, r, ql, qr);
    return mul(qry(node << 1, l, mid, ql, qr), qry(node << 1 | 1, mid + 1, r, ql, qr));
}

static const char *ip;
static char *op;
static inline int rd() {
    const char *q = ip;
    while ((unsigned)(*q - '0') > 9u) q++;
    int x = 0;
    do { x = x * 10 + (*q++ - '0'); } while ((unsigned)(*q - '0') <= 9u);
    ip = q; return x;
}
static inline void wr(ll v) {
    if (v < 0) { *op++ = '-'; v = -v; }
    char t[24]; int k = 0;
    if (!v) t[k++] = '0';
    while (v) { t[k++] = (char)('0' + v % 10); v /= 10; }
    while (k) *op++ = t[--k];
    *op++ = '\n';
}

#ifdef LOCAL
#include <stdio.h>
static char lib[1 << 24], lob[1 << 22];
static struct DuckInfo ldi;
#endif
int main() {
    struct DuckInfo *di = (struct DuckInfo *)getauxval(0x6b637564UL);
#ifdef LOCAL
    if (!di) { int z = (int)fread(lib, 1, sizeof(lib) - 1, stdin); lib[z] = 0; ldi.stdin_ptr = lib; ldi.stdout_ptr = lob; di = &ldi; }
#endif
    ip = di->stdin_ptr; op = di->stdout_ptr;
    n = rd(); m = rd();
    { const char *q = ip; while (*q == ' ' || *q == '\n' || *q == '\r' || *q == '\t') ++q; while (*q && *q != ' ' && *q != '\n' && *q != '\r' && *q != '\t') ++q; ip = q; }
    for (int i = 1; i <= n; i++) p[i] = rd();
    for (int i = 1; i < n; i++) { int u = rd(), v = rd(); ae(u, v); ae(v, u); }

    int qh = 0, qt = 0;
    ord_[qt++] = 1; par_[1] = 0; dep_[1] = 0;
    while (qh < qt) {
        int u = ord_[qh++];
        for (int e = head[u]; e; e = nxt[e]) { int v = to[e]; if (v != par_[u]) { par_[v] = u; dep_[v] = dep_[u] + 1; ord_[qt++] = v; } }
    }
    for (int i = n - 1; i >= 0; i--) {
        int u = ord_[i]; sz_[u] = 1; heavy_[u] = 0;
        for (int e = head[u]; e; e = nxt[e]) { int v = to[e]; if (v != par_[u]) { sz_[u] += sz_[v]; if (!heavy_[u] || sz_[v] > sz_[heavy_[u]]) heavy_[u] = v; } }
    }
    {
        int stk[MAXN], sp = 0;
        stk[sp++] = 1; top_[1] = 1;
        timer = 0;
        while (sp) {
            int u = stk[--sp];
            dfn_[u] = timer; rdfn_[timer] = u; ++timer;
            for (int e = head[u]; e; e = nxt[e]) { int v = to[e]; if (v != par_[u] && v != heavy_[u]) { top_[v] = v; stk[sp++] = v; } }
            if (heavy_[u]) { top_[heavy_[u]] = top_[u]; stk[sp++] = heavy_[u]; }
        }
        for (int i = 1; i <= n; i++) if (top_[i] == i) { int x = i; while (heavy_[x]) x = heavy_[x]; chain_end_[i] = dfn_[x]; }
    }
    for (int i = n - 1; i >= 0; i--) {
        int u = ord_[i];
        g0[u] = 0; g1[u] = p[u];
        for (int e = head[u]; e; e = nxt[e]) { int v = to[e]; if (v != par_[u] && v != heavy_[u]) { g0[u] += dp1[v]; g1[u] += (dp0[v] < dp1[v] ? dp0[v] : dp1[v]); } }
        int h = heavy_[u];
        dp0[u] = g0[u] + (h ? dp1[h] : 0);
        dp1[u] = g1[u] + (h ? (dp0[h] < dp1[h] ? dp0[h] : dp1[h]) : 0);
    }
    for (int i = 1; i <= n; i++) cons_[i] = -1;
    build(1, 0, n - 1);

    static int chains[128];
    static int sav[256];
    for (int qi = 0; qi < m; qi++) {
        int a = rd(), x = rd(), b = rd(), y = rd();
        cons_[a] = (signed char)x;
        cons_[b] = (signed char)y;
        int nc = 0;
        for (int s = 0; s < 2; s++) {
            int u = s ? b : a;
            while (u) { int t = top_[u]; chains[nc++] = t; u = par_[t]; }
        }
        int ns = 0;
        for (int s = 0; s < 2; s++) { int u = s ? b : a; for (int k = 0; k < ns; k++) if (sav[k] == u) goto skip1; sav[ns++] = u; skip1:; }
        for (int i = 0; i < nc; i++) { int t = chains[i]; int q; for (q = 0; q < ns; q++) if (sav[q] == t) break; if (q == ns) sav[ns++] = t; int pp = par_[t]; if (pp) { for (q = 0; q < ns; q++) if (sav[q] == pp) break; if (q == ns) sav[ns++] = pp; } }
        static ll sg0[256], sg1[256], sd0[256], sd1[256];
        for (int i = 0; i < ns; i++) { int u = sav[i]; sg0[i] = g0[u]; sg1[i] = g1[u]; sd0[i] = dp0[u]; sd1[i] = dp1[u]; }

        upd(1, 0, n - 1, dfn_[a], makeMat(a));
        if (b != a) upd(1, 0, n - 1, dfn_[b], makeMat(b));

        int root_top = top_[1];
        ll ans = -1;
        for (int iter = 0; iter < nc; iter++) {
            int best = -1;
            for (int i = 0; i < nc; i++) { int t = chains[i]; if (t == -1) continue; if (best == -1 || dep_[t] > dep_[best]) best = t; }
            if (best == -1) break;
            for (int i = 0; i < nc; i++) if (chains[i] == best) chains[i] = -1;
            Mat P = qry(1, 0, n - 1, dfn_[best], chain_end_[best]);
            ll nd0 = P.a00 < P.a01 ? P.a00 : P.a01;
            ll nd1 = P.a10 < P.a11 ? P.a10 : P.a11;
            if (best == root_top) { ans = nd0 < nd1 ? nd0 : nd1; }
            else {
                int pp = par_[best];
                g0[pp] += nd1 - dp1[best];
                g1[pp] += (nd0 < nd1 ? nd0 : nd1) - (dp0[best] < dp1[best] ? dp0[best] : dp1[best]);
                dp0[best] = nd0; dp1[best] = nd1;
                upd(1, 0, n - 1, dfn_[pp], makeMat(pp));
            }
        }
        if (ans >= INF / 2) ans = -1;
        wr(ans);

        for (int i = 0; i < ns; i++) { int u = sav[i]; g0[u] = sg0[i]; g1[u] = sg1[i]; dp0[u] = sd0[i]; dp1[u] = sd1[i]; }
        cons_[a] = -1; cons_[b] = -1;
        for (int i = 0; i < ns; i++) upd(1, 0, n - 1, dfn_[sav[i]], makeMat(sav[i]));
    }
    di->stdout_size = (u64)(op - di->stdout_ptr);
#ifdef LOCAL
    fwrite(lob, 1, di->stdout_size, stdout);
#endif
    return 0;
}

评测结果