代码

// 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; }

static Mat (*E)[MAXN];   // [LOG][MAXN]

// 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
    for (int v = 1; v <= n; v++) up[0][v] = par[v];
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++) { int x = up[k - 1][v]; up[k][v] = x ? up[k - 1][x] : 0; }

    E = (Mat (*)[MAXN])malloc(sizeof(Mat) * (size_t)LOG * MAXN);
    for (int v = 1; v <= n; v++) { Mat I = ident(); E[0][v] = I; }
    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
        E[0][v] = M;
    }
    for (int k = 1; k < LOG; k++) {
        for (int v = 1; v <= n; v++) {
            int x = up[k - 1][v];
            if (!x) { Mat I = ident(); E[k][v] = I; continue; }
            E[k][v] = mul(E[k - 1][v], E[k - 1][x]);
        }
    }

    // helpers
    static string out;
    out.reserve((size_t)m * 10);
    char tmp[32];
    Mat CM = edgeMat();
    for (int qi = 0; qi < m; qi++) {
        int a = (int)rdint(), x = (int)rdint(), b = (int)rdint(), y = (int)rdint();
        // LCA
        int u = a, v = b;
        if (dep[u] < dep[v]) { int t = u; u = v; v = t; }
        int diff = dep[u] - dep[v];
        for (int k = 0; k < LOG; k++) if ((diff >> k) & 1) u = up[k][u];
        int l;
        if (u == v) l = u;
        else {
            for (int k = LOG - 1; k >= 0; k--) if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
            l = par[u];
        }
        ll ans;
        if (l == a || l == b) {
            // one endpoint is the ancestor of the other
            int lo = (l == a) ? b : a;   // descendant
            int lox = (l == a) ? y : x;  // its forced state
            int lx = (l == a) ? x : y;   // ancestor's forced state
            int d = dep[lo] - dep[l];
            // child of l toward lo
            int c = lo;
            for (int k = 0; k < LOG; k++) if (((d - 1) >> k) & 1) c = up[k][c];
            // product over (d-1) steps from lo
            Mat res = ident();
            int cur = lo, rem = d - 1;
            for (int k = LOG - 1; k >= 0; k--) if (rem >= (1 << k)) { res = mul(res, E[k][cur]); cur = up[k][cur]; rem -= (1 << k); }
            Mat full = mul(res, CM);
            ll sub = (lox == 0) ? (lx == 0 ? full.a00 : full.a01) : (lx == 0 ? full.a10 : full.a11);
            ll val = addc((lox == 0 ? dp0[lo] : dp1[lo]), sub);
            ll excl = (lx == 0) ? dp1[c] : mn(dp0[c], dp1[c]);
            ans = addc(addc((lx == 0 ? W0[l] : W1[l]), (lx == 0 ? dp0[l] : dp1[l]) - excl), val);
        } else {
            int da = dep[a] - dep[l], db = dep[b] - dep[l];
            int ca = a;
            for (int k = 0; k < LOG; k++) if (((da - 1) >> k) & 1) ca = up[k][ca];
            int cb = b;
            for (int k = 0; k < LOG; k++) if (((db - 1) >> k) & 1) cb = up[k][cb];
            Mat resA = ident();
            { int cur = a, rem = da - 1;
              for (int k = LOG - 1; k >= 0; k--) if (rem >= (1 << k)) { resA = mul(resA, E[k][cur]); cur = up[k][cur]; rem -= (1 << k); } }
            Mat resB = ident();
            { int cur = b, rem = db - 1;
              for (int k = LOG - 1; k >= 0; k--) if (rem >= (1 << k)) { resB = mul(resB, E[k][cur]); cur = up[k][cur]; rem -= (1 << k); } }
            Mat fullA = mul(resA, CM), fullB = mul(resB, CM);
            ans = INF;
            for (int j = 0; j < 2; j++) {
                ll va = addc((x == 0 ? dp0[a] : dp1[a]), (x == 0 ? (j == 0 ? fullA.a00 : fullA.a01) : (j == 0 ? fullA.a10 : fullA.a11)));
                ll vb = addc((y == 0 ? dp0[b] : dp1[b]), (y == 0 ? (j == 0 ? fullB.a00 : fullB.a01) : (j == 0 ? fullB.a10 : fullB.a11)));
                ll exa = (j == 0) ? dp1[ca] : mn(dp0[ca], dp1[ca]);
                ll exb = (j == 0) ? dp1[cb] : mn(dp0[cb], dp1[cb]);
                ll base = (j == 0) ? cs0[l] : addc(p_[l], cs1[l]);
                ll v = addc(addc(addc(va, vb), base - exa - exb), (j == 0 ? W0[l] : W1[l]));
                if (v < ans) ans = v;
            }
        }
        if (ans >= INF / 2) { out += "-1\n"; }
        else { int l2 = sprintf(tmp, "%lld\n", ans); out.append(tmp, l2); }
    }
    fwrite(out.data(), 1, out.size(), stdout);
    if (DUMPIDX >= 0) {
        ull v = 0;
        if (DUMPIDX < 4) v = ((ull)out.size() >> (8 * (DUMPIDX & 3))) & 0xFFULL;
        else v = (DUMPIDX - 4 < (int)out.size()) ? (unsigned char)out[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

评测结果