代码

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

struct Jmp { ll a00, a01, a10, a11; int anc; int pad; };
static Jmp (*E)[MAXN];   // [LOG][MAXN] : matrix for 2^k steps + the 2^k-th ancestor

// apply matrix M to row-vector v: v'[j] = min(v[0]+M.a0j, v[1]+M.a1j)
static inline void vmul(ll *v, const Jmp &M) {
    ll n0 = mn(addc(v[0], M.a00), addc(v[1], M.a10));
    ll n1 = mn(addc(v[0], M.a01), addc(v[1], M.a11));
    v[0] = n0; v[1] = n1;
}

// 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 = (Jmp (*)[MAXN])malloc(sizeof(Jmp) * (size_t)LOG * MAXN);
    for (int v = 1; v <= n; v++) { E[0][v].a00 = 0; E[0][v].a11 = 0; E[0][v].a01 = INF; E[0][v].a10 = INF; E[0][v].anc = par[v]; }
    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].a00 = M.a00; E[0][v].a01 = M.a01; E[0][v].a10 = M.a10; E[0][v].a11 = M.a11;
        E[0][v].anc = par[v];
    }
    for (int k = 1; k < LOG; k++) {
        for (int v = 1; v <= n; v++) {
            int x = up[k - 1][v];
            if (!x) { E[k][v].a00 = 0; E[k][v].a11 = 0; E[k][v].a01 = INF; E[k][v].a10 = INF; E[k][v].anc = 0; continue; }
            Mat A; A.a00 = E[k-1][v].a00; A.a01 = E[k-1][v].a01; A.a10 = E[k-1][v].a10; A.a11 = E[k-1][v].a11;
            Mat B; B.a00 = E[k-1][x].a00; B.a01 = E[k-1][x].a01; B.a10 = E[k-1][x].a10; B.a11 = E[k-1][x].a11;
            Mat C = mul(A, B);
            E[k][v].a00 = C.a00; E[k][v].a01 = C.a01; E[k][v].a10 = C.a10; E[k][v].a11 = C.a11;
            E[k][v].anc = up[k][v];
        }
    }

    // Euler tour + sparse table RMQ for O(1) LCA
    static int euler[2 * MAXN], first_[MAXN], edep[2 * MAXN], lg2[2 * MAXN];
    static int *stt[18];
    {
        int ec = 0;
        // iterative DFS producing the Euler tour
        static int it_[MAXN];
        for (int v = 1; v <= n; v++) { it_[v] = head[v]; first_[v] = -1; }
        int stack_[MAXN], sp = 0;
        stack_[sp++] = 1; edep[0] = 0; euler[0] = 1; first_[1] = 0; ec = 1;
        while (sp) {
            int u = stack_[sp - 1];
            int e = it_[u];
            if (e == -1) { sp--; if (sp) { euler[ec] = stack_[sp - 1]; edep[ec] = dep[euler[ec]]; ec++; } continue; }
            it_[u] = nxt[e];
            int v = to_[e];
            if (v == par[u]) continue;
            stack_[sp++] = v;
            first_[v] = ec;
            euler[ec] = v; edep[ec] = dep[v]; ec++;
        }
        lg2[1] = 0;
        for (int i = 2; i <= ec; i++) lg2[i] = lg2[i >> 1] + 1;
        int L = lg2[ec] + 1;
        stt[0] = euler;
        for (int k = 1; k < L; k++) {
            int len = ec - (1 << k) + 1;
            stt[k] = (int *)malloc(sizeof(int) * len);
            int *cur = stt[k], *prv = stt[k - 1];
            for (int i = 0; i < len; i++) {
                int x = prv[i], y = prv[i + (1 << (k - 1))];
                cur[i] = (dep[x] <= dep[y]) ? x : y;
            }
        }
    }
    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 via Euler RMQ
        int l;
        {
            int x = first_[a], y = first_[b];
            if (x > y) { int t = x; x = y; y = t; }
            int k = lg2[y - x + 1];
            int n1 = stt[k][x], n2 = stt[k][y - (1 << k) + 1];
            l = (dep[n1] <= dep[n2]) ? n1 : n2;
        }
        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];
            // walk (d-1) steps up from lo; the final node is the child of l
            ll vv[2];
            vv[0] = (lox == 0) ? dp0[lo] : INF;
            vv[1] = (lox == 0) ? INF : dp1[lo];
            int cur = lo, rem = d - 1;
            for (int k = LOG - 1; k >= 0; k--) if (rem >= (1 << k)) { vmul(vv, E[k][cur]); cur = E[k][cur].anc; rem -= (1 << k); }
            int c = cur;
            { Jmp C; C.a00 = INF; C.a01 = 0; C.a10 = 0; C.a11 = 0; C.anc = 0; vmul(vv, C); }
            ll sub = (lx == 0) ? vv[0] : vv[1];
            ll val = 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];
            ll va2[2], vb2[2];
            va2[0] = (x == 0) ? dp0[a] : INF;
            va2[1] = (x == 0) ? INF : dp1[a];
            int ca;
            { int cur = a, rem = da - 1;
              for (int k = LOG - 1; k >= 0; k--) if (rem >= (1 << k)) { vmul(va2, E[k][cur]); cur = E[k][cur].anc; rem -= (1 << k); }
              ca = cur; }
            vb2[0] = (y == 0) ? dp0[b] : INF;
            vb2[1] = (y == 0) ? INF : dp1[b];
            int cb;
            { int cur = b, rem = db - 1;
              for (int k = LOG - 1; k >= 0; k--) if (rem >= (1 << k)) { vmul(vb2, E[k][cur]); cur = E[k][cur].anc; rem -= (1 << k); }
              cb = cur; }
            { Jmp C; C.a00 = INF; C.a01 = 0; C.a10 = 0; C.a11 = 0; C.anc = 0; vmul(va2, C); vmul(vb2, C); }
            ans = INF;
            for (int j = 0; j < 2; j++) {
                ll va = va2[j];
                ll vb = vb2[j];
                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;
}

评测结果