代码

// This code is AI-generated. (AI 生成的代码)
// NOIP2018 保卫王国: minimum-weight vertex cover with two forced vertices.
// Instead of re-running a dynamic DP per query, precompute the unconstrained
// subtree DP f[u][*] and the outside DP g[u][*].  Each HLD edge (parent,u)
// carries a (min,+) difference matrix; the segment tree stores their products
// in reverse HLD order.  A query accumulates the path contributions from a and
// b up to their LCA and combines them with the precomputed f and g, so it is
// O(log n) with no segment-tree updates.
#include <sys/auxv.h>
#include <stdint.h>
#include <stdlib.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)1e18;

static int n, mq;
static ll pw[MAXN];
static int head[MAXN], to[2 * MAXN], nxt[2 * MAXN], ec;
static int parent_[MAXN], dep_[MAXN], order_[MAXN];
static ll f[MAXN][2], g[MAXN][2];
static int sz_[MAXN], heavy_[MAXN], hhead_[MAXN], mp_[MAXN], posNode_[MAXN];
static ll leaf_[MAXN][2];
static ll segint_[MAXN][4];

static inline ll mn(ll a, ll b) { return a < b ? a : b; }

static inline int rd(const char **pp) {
    const char *p = *pp;
    while (*p <= ' ') ++p;
    int x = *p++ - '0';
    while (*p >= '0' && *p <= '9') x = x * 10 + (*p++ - '0');
    *pp = p;
    return x;
}
static inline void wr(char **pp, ll v) {
    char *o = *pp, t[24]; int k = 0;
    if (v < 0) { *o++ = 0x2d; v = -v; }
    if (!v) t[k++] = '0';
    while (v) { t[k++] = (char)('0' + v % 10); v /= 10; }
    while (k) *o++ = t[--k];
    *o++ = '\n';
    *pp = o;
}

static inline void mmul(ll C[4], const ll A[4], const ll B[4]) {
    ll a00 = A[0], a01 = A[1], a10 = A[2], a11 = A[3];
    ll b00 = B[0], b01 = B[1], b10 = B[2], b11 = B[3];
    C[0] = mn(a00 + b00, a01 + b10);
    C[1] = mn(a00 + b01, a01 + b11);
    C[2] = mn(a10 + b00, a11 + b10);
    C[3] = mn(a10 + b01, a11 + b11);
}
static inline void getmat(int node, ll M[4]) {
    if (node >= n) {
        int L = node - n;
        int u = posNode_[n - 1 - L];
        if (parent_[u] == 0) { M[0] = 0; M[1] = INF; M[2] = INF; M[3] = 0; }
        else { M[0] = INF; M[1] = leaf_[L][1]; M[2] = leaf_[L][0]; M[3] = leaf_[L][1]; }
    } else {
        M[0] = segint_[node][0]; M[1] = segint_[node][1];
        M[2] = segint_[node][2]; M[3] = segint_[node][3];
    }
}
static inline void appleaf(ll &v0, ll &v1, int L) {
    if (L == n - 1) return;
    ll h0 = leaf_[L][0], h1 = leaf_[L][1];
    ll n0 = v1 + h0;
    ll n1 = mn(v0, v1) + h1;
    v0 = n0; v1 = n1;
}
static inline void appnode(ll &v0, ll &v1, int node) {
    if (node >= n) { appleaf(v0, v1, node - n); return; }
    ll *M = segint_[node];
    ll n0 = mn(v0 + M[0], v1 + M[2]);
    ll n1 = mn(v0 + M[1], v1 + M[3]);
    v0 = n0; v1 = n1;
}
static inline void qdesc_vec(ll &v0, ll &v1, int l, int r) {
    if (l > r) return;
    if (l == r) { appleaf(v0, v1, l - 1); return; }
    int lo = l - 1 + n, hi = r + n;
    int stk[40], top = 0;
    while (lo < hi) {
        if (lo & 1) { appnode(v0, v1, lo); ++lo; }
        if (hi & 1) { --hi; stk[top++] = hi; }
        lo >>= 1; hi >>= 1;
    }
    while (top) appnode(v0, v1, stk[--top]);
}
static inline void excl_vec(int x, int y, ll &v0, ll &v1) {
    if (mp_[y] <= mp_[x]) return;
    qdesc_vec(v0, v1, n - mp_[y], n - mp_[x] - 1);
}
static inline void full_vec(int x, int y, ll &v0, ll &v1) {
    if (mp_[y] < mp_[x]) return;
    qdesc_vec(v0, v1, n - mp_[y], n - mp_[x]);
}
static inline void ae(int u, int v) { to[++ec] = v; nxt[ec] = head[u]; head[u] = ec; }

#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
    const char *p = di->stdin_ptr;
    char *o = di->stdout_ptr;
    n = rd(&p); mq = rd(&p);
    while (*p == ' ' || *p == '\t' || *p == '\r') ++p;
    while (*p && *p != ' ' && *p != '\t' && *p != '\n' && *p != '\r') ++p;
    for (int i = 1; i <= n; ++i) pw[i] = rd(&p);
    for (int i = 1; i < n; ++i) { int u = rd(&p), v = rd(&p); ae(u, v); ae(v, u); }

    int qh = 0, qt = 0;
    order_[qt++] = 1; parent_[1] = 0; dep_[1] = 0;
    while (qh < qt) {
        int u = order_[qh++];
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == parent_[u]) continue;
            parent_[v] = u; dep_[v] = dep_[u] + 1; order_[qt++] = v;
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        int u = order_[i];
        ll s0 = 0, s1 = pw[u];
        sz_[u] = 1; heavy_[u] = 0; int best = 0;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == parent_[u]) continue;
            s0 += f[v][1];
            s1 += mn(f[v][0], f[v][1]);
            sz_[u] += sz_[v];
            if (sz_[v] > best) { best = sz_[v]; heavy_[u] = v; }
        }
        f[u][0] = s0; f[u][1] = s1;
    }
    g[1][0] = 0; g[1][1] = 0;
    for (int i = 0; i < n; ++i) {
        int u = order_[i];
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == parent_[u]) continue;
            ll mc = mn(f[v][0], f[v][1]);
            g[v][0] = g[u][1] + f[u][1] - mc;
            g[v][1] = mn(g[u][0] + f[u][0] - f[v][1], g[u][1] + f[u][1] - mc);
        }
    }
    int cur = 0;
    for (int i = 0; i < n; ++i) {
        int u = order_[i];
        if (parent_[u] == 0 || heavy_[parent_[u]] != u) {
            int x = u;
            while (x != 0) { hhead_[x] = u; mp_[x] = cur; posNode_[cur] = x; ++cur; x = heavy_[x]; }
        }
    }
    for (int L = 0; L < n; ++L) {
        int u = posNode_[n - 1 - L];
        if (parent_[u] == 0) { leaf_[L][0] = 0; leaf_[L][1] = 0; }
        else {
            int pu = parent_[u];
            leaf_[L][0] = f[pu][0] - f[u][1];
            leaf_[L][1] = f[pu][1] - mn(f[u][0], f[u][1]);
        }
    }
    for (int i = n - 1; i >= 1; --i) {
        ll A[4], B[4];
        getmat(i << 1, A);
        getmat(i << 1 | 1, B);
        mmul(segint_[i], A, B);
    }

    for (int qi = 0; qi < mq; ++qi) {
        int a = rd(&p), xa = rd(&p), b = rd(&p), xb = rd(&p);
        int u = a, v = b;
        ll Va0 = xa == 0 ? 0 : INF, Va1 = xa == 1 ? 0 : INF;
        ll Vb0 = xb == 0 ? 0 : INF, Vb1 = xb == 1 ? 0 : INF;
        while (hhead_[u] != hhead_[v]) {
            if (dep_[hhead_[u]] > dep_[hhead_[v]]) {
                full_vec(hhead_[u], u, Va0, Va1);
                u = parent_[hhead_[u]];
            } else {
                full_vec(hhead_[v], v, Vb0, Vb1);
                v = parent_[hhead_[v]];
            }
        }
        int L = dep_[u] < dep_[v] ? u : v;
        excl_vec(L, u, Va0, Va1);
        excl_vec(L, v, Vb0, Vb1);
        ll fac = f[a][xa], fbc = f[b][xb];
        ll best = INF;
        if (!((a == L && xa != 0) || (b == L && xb != 0))) {
            ll c = Va0 + Vb0 - f[L][0] + fac + fbc + g[L][0];
            if (c < best) best = c;
        }
        if (!((a == L && xa != 1) || (b == L && xb != 1))) {
            ll c = Va1 + Vb1 - f[L][1] + fac + fbc + g[L][1];
            if (c < best) best = c;
        }
        wr(&o, best >= INF / 2 ? -1 : best);
    }
    di->stdout_size = (u64)(o - di->stdout_ptr);
#ifdef LOCAL
    fwrite(lob, 1, di->stdout_size, stdout);
#endif
    return 0;
}

评测结果