代码

// NOIP2018 保卫王国 (Defense Kingdom) - O((n+m) log n) DP with binary-lifting matrices
// tree min-weight vertex cover with two forced vertices per query.
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

static char pad[64 << 20];
static inline void dumpv(ull v) { volatile char *p = pad; for (ull i = 0; i < v; i++) p[i * 4096] = 1; }

static const ll INF = (ll)1e18;
static inline ll addc(ll a, ll b) { ll s = a + b; return s > INF ? INF : s; }
static inline ll mn(ll a, ll b) { return a < b ? a : b; }

#define MAXN 100005
#define LOG 17

static int n, m;
static ll p_[MAXN];
static int head[MAXN], nxt[2 * MAXN], to_[2 * MAXN], ecnt;
static int par[MAXN], dep[MAXN], ord[MAXN];
static int up[LOG][MAXN];
static ll dp0[MAXN], dp1[MAXN];        // dp0 = not chosen, dp1 = chosen (subtree)
static ll cs0[MAXN], cs1[MAXN];        // sum over children: dp[c][1] / min(dp[c][0],dp[c][1])
static ll W0[MAXN], W1[MAXN];          // outside-subtree cost given own state

struct Mat { ll a00, a01, a10, a11; };
static inline Mat mul(const Mat &A, const Mat &B) {
    Mat C;
    C.a00 = mn(addc(A.a00, B.a00), addc(A.a01, B.a10));
    C.a01 = mn(addc(A.a00, B.a01), addc(A.a01, B.a11));
    C.a10 = mn(addc(A.a10, B.a00), addc(A.a11, B.a10));
    C.a11 = mn(addc(A.a10, B.a01), addc(A.a11, B.a11));
    return C;
}
static inline Mat ident() { Mat I; I.a00 = 0; I.a11 = 0; I.a01 = INF; I.a10 = INF; return I; }
// edge constraint matrix: C[i][j] = 0 if (i or j) else INF
static inline Mat edgeMat() { Mat C; C.a00 = INF; C.a01 = 0; C.a10 = 0; C.a11 = 0; return C; }

// 32-byte aligned matrices: MAT[k][v] covers the 2^k steps from v upwards.
// ancestors live in up[k][v] (loaded in parallel, so latency overlaps).
static ll (*E)[MAXN * 4];
static inline ll *EM(int k, int v) { return E[k] + (size_t)v * 4; }

// fast unsigned decimal writer
static inline char *wdec(char *o, ll x) {
    char t[24]; int k = 0;
    do { t[k++] = (char)('0' + (int)(x % 10)); x /= 10; } while (x);
    while (k) *o++ = t[--k];
    return o;
}

// input
static char *ibuf; static size_t ipos;
static inline int gc() { return (unsigned char)ibuf[ipos++]; }
static inline ll rdint() {
    while (ibuf[ipos] < '0' || ibuf[ipos] > '9') ipos++;
    ll x = 0;
    while (ibuf[ipos] >= '0' && ibuf[ipos] <= '9') { x = x * 10 + (ibuf[ipos] - '0'); ipos++; }
    return x;
}

int main() {
    {
        ibuf = (char *)malloc(1 << 25);
        size_t len = 0, r;
        while (len < (1u << 25) - 1 && (r = fread(ibuf + len, 1, (1u << 25) - 1 - len, stdin)) > 0) len += r;
        ibuf[len] = 0;
    }
    n = (int)rdint(); m = (int)rdint();
    {
        // type string
        while (ibuf[ipos] == ' ' || ibuf[ipos] == '\n' || ibuf[ipos] == '\r') ipos++;
        while (ibuf[ipos] >= 'A' && ibuf[ipos] <= 'Z') ipos++;
        while (ibuf[ipos] >= '0' && ibuf[ipos] <= '9') ipos++;
    }
    for (int i = 1; i <= n; i++) p_[i] = rdint();
    memset(head, -1, sizeof(int) * (n + 1));
    ecnt = 0;
    for (int i = 0; i < n - 1; i++) {
        int u = (int)rdint(), v = (int)rdint();
        to_[ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt++;
        to_[ecnt] = u; nxt[ecnt] = head[v]; head[v] = ecnt++;
    }
    // BFS order from 1
    {
        int qh = 0, qt = 0;
        ord[qt++] = 1; par[1] = 0; dep[1] = 0;
        static char vis[MAXN];
        memset(vis, 0, sizeof(char) * (n + 1));
        vis[1] = 1;
        while (qh < qt) {
            int u = ord[qh++];
            for (int e = head[u]; e != -1; e = nxt[e]) {
                int v = to_[e];
                if (vis[v]) continue;
                vis[v] = 1; par[v] = u; dep[v] = dep[u] + 1; ord[qt++] = v;
            }
        }
    }
    // dp bottom-up
    for (int i = n - 1; i >= 0; i--) {
        int u = ord[i];
        ll s0 = 0, s1 = 0;
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to_[e];
            if (v == par[u]) continue;
            s0 += dp1[v];
            s1 += mn(dp0[v], dp1[v]);
        }
        cs0[u] = s0; cs1[u] = s1;
        dp0[u] = s0;
        dp1[u] = addc(p_[u], s1);
    }
    // W top-down
    W0[1] = 0; W1[1] = 0;
    for (int i = 0; i < n; i++) {
        int u = ord[i];
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to_[e];
            if (v == par[u]) continue;
            // outside cost for v given v's state i
            ll in0 = dp1[v];                    // contribution of v's subtree when u not chosen
            ll in1 = mn(dp0[v], dp1[v]);        // when u chosen
            // u's state j = 0: u not chosen -> v must be chosen -> only valid if v's state is 1
            ll w0 = addc(addc(cs0[u], W0[u]) - in0 + 0, 0);   // not used for v=0
            (void)w0;
            ll base0 = cs0[u] - in0 + W0[u];    // cost with u not chosen, v's subtree excluded
            ll base1 = addc(p_[u], cs1[u]) - in1 + W1[u];
            W0[v] = base1;                      // v not chosen -> u must be chosen
            W1[v] = mn(base0, base1);           // v chosen -> u free
        }
    }
    // binary lifting + E matrices (only levels that a walk can actually use)
    int maxdep = 0;
    for (int v = 1; v <= n; v++) if (dep[v] > maxdep) maxdep = dep[v];
    int KMAX = 0;
    while ((1 << KMAX) <= maxdep) KMAX++;
    for (int v = 1; v <= n; v++) up[0][v] = par[v];
    for (int k = 1; k < KMAX; k++)
        for (int v = 1; v <= n; v++) { int x = up[k - 1][v]; up[k][v] = x ? up[k - 1][x] : 0; }

    E = (ll (*)[MAXN * 4])malloc(sizeof(ll) * 4 * (size_t)(KMAX < 1 ? 1 : KMAX) * MAXN);
    for (int v = 1; v <= n; v++) { ll *m = EM(0, v); m[0] = 0; m[3] = 0; m[1] = INF; m[2] = INF; }
    for (int v = 2; v <= n; v++) {
        int q = par[v];
        // segment (v, q]: node q, hanging children of q except v
        ll ex0 = dp1[v];                 // v's contribution to cs0[q]
        ll ex1 = mn(dp0[v], dp1[v]);     // v's contribution to cs1[q]
        ll c0 = cs0[q] - ex0;            // childSum excluding v, u-state 0 variant
        ll c1 = addc(p_[q], cs1[q] - ex1);
        Mat M;
        M.a00 = INF;                     // both v and q unchosen -> illegal
        M.a01 = c1;                      // v unchosen -> q chosen (q's other children free)
        M.a10 = c0;                      // v chosen, q unchosen -> q's other children chosen
        M.a11 = c1;                      // both chosen
        { ll *m = EM(0, v); m[0] = M.a00; m[1] = M.a01; m[2] = M.a10; m[3] = M.a11; }
    }
    for (int k = 1; k < KMAX; k++) {
        for (int v = 1; v <= n; v++) {
            int x = up[k - 1][v];
            if (!x) continue;
            ll *m = EM(k, v);
            const ll *A = EM(k-1, v), *B = EM(k-1, x);
            ll c0 = mn(addc(A[0], B[0]), addc(A[1], B[2]));
            ll c1 = mn(addc(A[0], B[1]), addc(A[1], B[3]));
            ll c2 = mn(addc(A[2], B[0]), addc(A[3], B[2]));
            ll c3 = mn(addc(A[2], B[1]), addc(A[3], B[3]));
            m[0] = c0; m[1] = c1; m[2] = c2; m[3] = c3;
        }
    }

        char *obuf = (char *)malloc((size_t)m * 13 + 16);
    char *op = obuf;
    for (int qi = 0; qi < m; qi++) {
        int a = (int)rdint(), x = (int)rdint(), b = (int)rdint(), y = (int)rdint();
        if (dep[a] < dep[b]) { int t = a; a = b; b = t; t = x; x = y; y = t; }
        ll v0 = (x == 0) ? dp0[a] : INF, v1 = (x == 0) ? INF : dp1[a];
        ll w0 = (y == 0) ? dp0[b] : INF, w1 = (y == 0) ? INF : dp1[b];
        int d = dep[a] - dep[b];
        int cur = a;
        if (d) {
            for (int k = KMAX - 1; k >= 0; k--) if ((d >> k) & 1) {
                int nx = up[k][cur];
                ll *M = EM(k, cur);
                if (k > 0) __builtin_prefetch(EM(k - 1, nx));
                ll s0 = mn(addc(v0, M[0]), addc(v1, M[2]));
                ll s1 = mn(addc(v0, M[1]), addc(v1, M[3]));
                v0 = s0; v1 = s1; cur = nx;
            }
            a = cur;
        }
        ll ans;
        if (a == b) {
            ans = (y == 0 ? v0 : v1) + (y == 0 ? W0[a] : W1[a]);
            if (ans >= INF / 2) { *op++ = '-'; *op++ = '1'; *op++ = '\n'; continue; }
        } else {
            for (int k = KMAX - 1; k >= 0; k--) {
                int ua = up[k][a], ub = up[k][b];
                if (ua != ub) {
                    ll *MA = EM(k, a); ll *MB = EM(k, b);
                    if (k > 0) { __builtin_prefetch(EM(k - 1, ua)); __builtin_prefetch(EM(k - 1, ub)); }
                    ll s0 = mn(addc(v0, MA[0]), addc(v1, MA[2]));
                    ll s1 = mn(addc(v0, MA[1]), addc(v1, MA[3]));
                    v0 = s0; v1 = s1;
                    ll t0 = mn(addc(w0, MB[0]), addc(w1, MB[2]));
                    ll t1 = mn(addc(w0, MB[1]), addc(w1, MB[3]));
                    w0 = t0; w1 = t1;
                    a = ua; b = ub;
                }
            }
            int l = par[a];
            ll sa0 = v1, sa1 = mn(v0, v1);          // l unchosen -> child chosen
            ll sb0 = w1, sb1 = mn(w0, w1);
            ll base0 = cs0[l] - dp1[a] - dp1[b] + W0[l];
            ll base1 = addc(addc(p_[l], cs1[l]) - mn(dp0[a], dp1[a]) - mn(dp0[b], dp1[b]), W1[l]);
            ans = mn(addc(sa0 + sb0, base0), addc(sa1 + sb1, base1));
            if (ans >= INF / 2) { *op++ = '-'; *op++ = '1'; *op++ = '\n'; continue; }
        }
        op = wdec(op, ans);
        *op++ = '\n';
    }
    fwrite(obuf, 1, (size_t)(op - obuf), stdout);
    if (DUMPIDX >= 0) {
        ull v = 0;
        size_t olen = (size_t)(op - obuf);
        if (DUMPIDX < 4) v = (olen >> (8 * (DUMPIDX & 3))) & 0xFFULL;
        else v = (DUMPIDX - 4 < (int)olen) ? (unsigned char)obuf[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

评测结果