代码

// 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];
static int seen_[MAXN];
static int stamp_ = 0;

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 inline void applyMat(const Mat &M, ll &v0, ll &v1) {
    ll nv0 = M.a00 + v0 < M.a01 + v1 ? M.a00 + v0 : M.a01 + v1;
    ll nv1 = M.a10 + v0 < M.a11 + v1 ? M.a10 + v0 : M.a11 + v1;
    v0 = nv0; v1 = nv1;
}
// apply M_l * ... * M_r to (v0,v1): visit right child first
static void applyRange(int node, int l, int r, int ql, int qr, ll &v0, ll &v1) {
    if (ql <= l && r <= qr) { applyMat(seg[node], v0, v1); return; }
    int mid = (l + r) >> 1;
    if (qr > mid) applyRange(node << 1 | 1, mid + 1, r, ql, qr, v0, v1);
    if (ql <= mid) applyRange(node << 1, l, mid, ql, qr, v0, v1);
}
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], 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 pa[64], pb[64], na = 0, nb = 0;
        for (int u = a; u; u = par_[top_[u]]) pa[na++] = top_[u];
        for (int u = b; u; u = par_[top_[u]]) pb[nb++] = top_[u];
        int nc = 0, i = 0, j = 0;
        while (i < na || j < nb) {
            int t;
            if (j >= nb || (i < na && dep_[pa[i]] >= dep_[pb[j]])) t = pa[i++]; else t = pb[j++];
            if (nc == 0 || chains[nc - 1] != t) chains[nc++] = t;
        }
        ++stamp_;
        int ns = 0;
        {
#define SAVE(z) do { int zz=(z); if (seen_[zz] != stamp_) { seen_[zz] = stamp_; sav[ns++] = zz; } } while (0)
            SAVE(a); SAVE(b);
            for (int k = 0; k < nc; k++) { int t = chains[k]; SAVE(t); int pp = par_[t]; if (pp) SAVE(pp); }
#undef SAVE
        }
        static ll sg0[256], sg1[256], sd0[256], sd1[256];
        for (int k = 0; k < ns; k++) { int u = sav[k]; sg0[k] = g0[u]; sg1[k] = g1[u]; sd0[k] = dp0[u]; sd1[k] = 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 k = 0; k < nc; k++) {
            int t = chains[k];
            ll nd0 = 0, nd1 = 0;
            applyRange(1, 0, n - 1, dfn_[t], chain_end_[t], nd0, nd1);
            if (t == root_top) { ans = nd0 < nd1 ? nd0 : nd1; }
            else {
                int pp = par_[t];
                g0[pp] += nd1 - dp1[t];
                g1[pp] += (nd0 < nd1 ? nd0 : nd1) - (dp0[t] < dp1[t] ? dp0[t] : dp1[t]);
                dp0[t] = nd0; dp1[t] = nd1;
                upd(1, 0, n - 1, dfn_[pp], makeMat(pp));
            }
        }
        if (ans >= INF / 2) ans = -1;
        wr(ans);

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

评测结果