代码

// NOIP2018 保卫王国 - HLD + per-chain block range products (min-plus 2x2 matrices).
// Memory O(n): no n log n jump table. Per query: O(log n) chain hops, each O(1),
// and one O(1) partial range product (2 block prefix/suffix + 2 sparse-table lookups).
#include <cstdio>
#include <cstring>
#include <cstdlib>

typedef long long ll;
typedef unsigned long long ull;

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

// ---------------- I/O ----------------
struct DI {
    ull abi;
    const char *in; ull insz;
    char *out; ull outlim; ull outsz;
    char *err; ull errlim; ull errsz;
    const char *IB; ull IBlim;
    char *OB; ull OBlim;
    ull tscfreq;
} __attribute__((packed));

static const char *INP;
static ull INPOS = 0;
static char *OUTP;
static char *OUT_BASE;
#ifdef TEST_IO
static char *inbuf;
#else
#include <sys/auxv.h>
#endif

static inline void io_init() {
#ifdef TEST_IO
    static char buf[1 << 26];
    size_t got = fread(buf, 1, sizeof(buf), stdin);
    (void)got;
    inbuf = buf;
    INP = buf;
    static char obuf[1 << 25];
    OUTP = obuf; OUT_BASE = obuf;
#else
    struct DI *di = (struct DI *)getauxval(0x6b637564);
    INP = di->in;
    OUTP = di->out; OUT_BASE = di->out;
#endif
}

static inline int rdint() {
    const char *p = INP + INPOS;
    while (*p < '0' || *p > '9') p++;
    unsigned v = 0;
    ull x;
    __builtin_memcpy(&x, p, 8);
    ull bad = ((x ^ 0x3030303030303030ULL) + 0x7676767676767676ULL) & 0x8080808080808080ULL;
    int k = bad ? (int)(__builtin_ctzll(bad) >> 3) : 8;
    if (k) {
        int sh = 8 * (8 - k);
        ull xx = (x << sh) | (0x3030303030303030ULL & ((sh == 64) ? 0ULL : ((1ULL << sh) - 1ULL)));
        ull d = xx - 0x3030303030303030ULL;
        ull t = (d * 10 + (d >> 8)) & 0x00FF00FF00FF00FFULL;
        t = (t * 100 + (t >> 16)) & 0x0000FFFF0000FFFFULL;
        t = (t * 10000 + (t >> 32)) & 0xFFFFFFFFULL;
        v = (unsigned)t;
        p += k;
    } else {
        while (*p >= '0' && *p <= '9') { v = v * 10 + (unsigned)(*p - '0'); p++; }
    }
    INPOS = (ull)(p - INP);
    return (int)v;
}

static unsigned int D4W[10000];        // 4 ASCII digits of i, packed little endian
static char D4B[10000][4];
static void init_d4b() {
    for (int i = 0; i < 10000; i++) {
        char a = (char)('0' + i / 1000), b = (char)('0' + (i / 100) % 10);
        char c = (char)('0' + (i / 10) % 10), d = (char)('0' + i % 10);
        D4B[i][0] = a; D4B[i][1] = b; D4B[i][2] = c; D4B[i][3] = d;
        D4W[i] = (unsigned)a | ((unsigned)b << 8) | ((unsigned)c << 16) | ((unsigned)d << 24);
    }
}
// answers fit in 11 digits; write them with one 8-byte store
static inline void wnum(ll x) {
    if (x < 100000000LL) {
        unsigned hi = (unsigned)(x / 10000), lo = (unsigned)(x % 10000);
        unsigned long long w = (unsigned long long)D4W[hi] | ((unsigned long long)D4W[lo] << 32);
        int n = (x >= 10000000LL) ? 8 : (x >= 1000000LL) ? 7 : (x >= 100000LL) ? 6
              : (x >= 10000LL) ? 5 : (x >= 1000LL) ? 4 : (x >= 100LL) ? 3 : (x >= 10LL) ? 2 : 1;
        w >>= 8 * (8 - n);
        __builtin_memcpy(OUTP, &w, 8);
        OUTP += n;
        *OUTP++ = '\n';
    } else {
        unsigned h = (unsigned)(x / 100000000LL);
        unsigned m = (unsigned)((x / 10000) % 10000), l = (unsigned)(x % 10000);
        char tmp[20];
        __builtin_memcpy(tmp, D4B[h], 4);
        __builtin_memcpy(tmp + 4, D4B[m], 4);
        __builtin_memcpy(tmp + 8, D4B[l], 4);
        int n = (x >= 10000000000LL) ? 11 : (x >= 1000000000LL) ? 10 : 9;
        __builtin_memcpy(OUTP, tmp + 12 - n, 12);
        OUTP += n;
        *OUTP++ = '\n';
    }
}
// ---------------- data ----------------
#define MAXN 100005
static int n, m;
static ll p_[MAXN];
static int start_[MAXN + 2], adj_[2 * MAXN], deg_[MAXN + 1];
static int eu_[MAXN], ev_[MAXN];
static int par_[MAXN], dep_[MAXN], ord_[MAXN], sz_[MAXN], heavy_[MAXN];
static int head_[MAXN], pos_[MAXN], chainStart_[MAXN], nodeAt_[MAXN], cslot_[MAXN];
static int clen_[MAXN], nchain;
static ll DP_[2 * MAXN], WW_[2 * MAXN];       // (dp0,dp1) / (W0,W1) interleaved
static ll cs0_[MAXN], cs1_[MAXN];
static ll MC0_[MAXN], MC1_[MAXN];
static int suSlot_[MAXN], headDep_[MAXN], upHead_[MAXN];
static ll *SUF_;                              // product from slot up to its chain head (inclusive)

#define BSHIFT 5
#define BSIZE (1 << BSHIFT)
#define MAXBLK (MAXN + 16)
static int nblk;
struct Meta { int cIdx, spBase, spNb; };
static Meta META_[MAXN];
static int gblk_[MAXN];
static ll *BP_, *BS_, *PB_, *SP_, *SUF2_;

static inline void pf_(const void *p) { __asm__ __volatile__("prefetcht0 (%0)" :: "r"(p)); }
static inline void mmul(ll *C, const ll *A, const ll *B) {
    C[0] = mn(addc(A[0], B[0]), addc(A[1], B[2]));
    C[1] = mn(addc(A[0], B[1]), addc(A[1], B[3]));
    C[2] = mn(addc(A[2], B[0]), addc(A[3], B[2]));
    C[3] = mn(addc(A[2], B[1]), addc(A[3], B[3]));
}
static inline void edgeMat(ll *M, int slot) {
    M[0] = INF; M[1] = MC1_[slot]; M[2] = MC0_[slot]; M[3] = MC1_[slot];
}
static inline void applyMat(ll &v0, ll &v1, const ll *M) {
    ll s0 = mn(addc(M[0], v0), addc(M[2], v1));
    ll s1 = mn(addc(M[1], v0), addc(M[3], v1));
    v0 = s0; v1 = s1;
}
static inline void applyEdge(ll &v0, ll &v1, int slot) {
    ll c0 = MC0_[slot], c1 = MC1_[slot];
    ll n0 = addc(c0, v1);
    ll n1 = addc(c1, mn(v0, v1));
    v0 = n0;
    v1 = n1;
}
// apply composite of positions [l,r] (1-based in chain). Precondition: 2 <= l <= r <= L
static inline void applyRange(ll &v0, ll &v1, int cs, int l, int r) {
    int sl = cs + l - 1, sr = cs + r - 1;
    if (l == r) { applyEdge(v0, v1, sl); return; }
    if (META_[sl].cIdx == META_[sr].cIdx) {
        for (int i = sr; i >= sl; i--) applyEdge(v0, v1, i);
        return;
    }
    const ll *P1 = BP_ + (size_t)sr * 4;      // covers [blockFirst(br2), r]
    const ll *P3 = BS_ + (size_t)sl * 4;      // covers [l, blockLast(bl)]
    pf_(P1);
    pf_(P3);
    int j1 = META_[sl].cIdx, j2 = META_[sr].cIdx;
    int spBase = META_[sl].spBase, spNb = META_[sl].spNb;
    int lo = j1 + 1, hi = j2 - 1;
    const ll *P2a = 0, *P2b = 0;
    if (lo <= hi) {
        if (lo == hi) {
            P2a = SP_ + (size_t)(spBase + lo) * 4;
            P2b = P2a;
        } else {
            int k = 31 - __builtin_clz((unsigned)(lo ^ hi));
            int base = spBase + k * spNb;
            P2a = SP_ + (size_t)(base + lo) * 4;
            P2b = SP_ + (size_t)(base + hi) * 4;
        }
        pf_(P2a);
        pf_(P2b);
    }
    applyMat(v0, v1, P1);
    if (P2b) { applyMat(v0, v1, P2b); if (P2a != P2b) applyMat(v0, v1, P2a); }
    applyMat(v0, v1, P3);
}
// climb one whole chain: positions [1, p]
static inline void applyHop(ll &v0, ll &v1, int cs, int p) {
    if (p >= 2) applyRange(v0, v1, cs, 2, p);
    applyEdge(v0, v1, cs);
}


// Prefetch the block pieces for a query (1-query lookahead to hide DRAM latency).
static inline void prefetchQuery(int a, int b) {
    // walk the whole climb path, prefetching every chain-hop product
    while (head_[a] != head_[b]) {
        if (headDep_[a] > headDep_[b]) { pf_(SUF_ + (size_t)suSlot_[a] * 4); a = upHead_[a]; }
        else { pf_(SUF_ + (size_t)suSlot_[b] * 4); b = upHead_[b]; }
    }
    int pa = pos_[a], pb = pos_[b], l, r, cs;
    if (pa > pb) { l = pb + 1; r = pa; cs = chainStart_[a]; }
    else if (pa < pb) { l = pa + 1; r = pb; cs = chainStart_[b]; }
    else return;
    int sl = cs + l - 1, sr = cs + r - 1;
    int j1 = META_[sl].cIdx, j2 = META_[sr].cIdx;
    if (j1 == j2) return;
    pf_(BP_ + (size_t)sr * 4);
    pf_(BS_ + (size_t)sl * 4);
    int lo = j1 + 1, hi = j2 - 1;
    if (lo <= hi) {
        int spBase = META_[sl].spBase, spNb = META_[sl].spNb;
        if (lo == hi) {
            pf_(SP_ + (size_t)(spBase + lo) * 4);
        } else {
            int k = 31 - __builtin_clz((unsigned)(lo ^ hi));
            int base = spBase + k * spNb;
            pf_(SP_ + (size_t)(base + lo) * 4);
            pf_(SP_ + (size_t)(base + hi) * 4);
        }
    }
}
int main(int argc, char **argv) {
    (void)argc; (void)argv;
    init_d4b();
    io_init();
    n = rdint(); m = rdint();
    {
        while (INP[INPOS] == ' ' || INP[INPOS] == '\n' || INP[INPOS] == '\r') INPOS++;
        while (INP[INPOS] >= 'A' && INP[INPOS] <= 'Z') INPOS++;
        while (INP[INPOS] >= '0' && INP[INPOS] <= '9') INPOS++;
    }
    for (int i = 1; i <= n; i++) p_[i] = rdint();
    // CSR adjacency
    for (int i = 1; i <= n; i++) deg_[i] = 0;
    for (int i = 0; i < n - 1; i++) {
        int u = rdint(), v = rdint();
        deg_[u]++; deg_[v]++;
        eu_[i] = u; ev_[i] = v;
    }
    {
        int s = 0;
        for (int i = 1; i <= n; i++) { int d = deg_[i]; start_[i] = s; s += d; }
        start_[n + 1] = s;
        for (int i = 1; i <= n; i++) deg_[i] = start_[i];
        for (int i = 0; i < n - 1; i++) {
            int u = eu_[i], v = ev_[i];
            adj_[deg_[u]++] = v;
            adj_[deg_[v]++] = u;
        }
    }
    // BFS from 1
    {
        int qh = 0, qt = 0;
        ord_[qt++] = 1; par_[1] = 0; dep_[1] = 0;
        while (qh < qt) {
            int u = ord_[qh++];
            for (int e = start_[u]; e < start_[u + 1]; e++) {
                int v = adj_[e];
                if (v != par_[u]) { par_[v] = u; dep_[v] = dep_[u] + 1; ord_[qt++] = v; }
            }
        }
    }
    // subtree sizes + heavy child
    for (int i = 1; i <= n; i++) { sz_[i] = 1; heavy_[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {
        int u = ord_[i], q = par_[u];
        if (q) {
            sz_[q] += sz_[u];
            if (sz_[u] > sz_[heavy_[q]]) heavy_[q] = u;
        }
    }
    // HLD layout
    nchain = 0;
    {
        int slot = 0;
        for (int i = 0; i < n; i++) {
            int u = ord_[i];
            if (u == 1 || heavy_[par_[u]] != u) {
                nchain++;
                int cs = slot;
                cslot_[nchain] = cs;
                int L = 0;
                for (int v = u; v; v = heavy_[v]) {
                    head_[v] = u; pos_[v] = L + 1; chainStart_[v] = cs; nodeAt_[slot] = v;
                    suSlot_[v] = slot; headDep_[v] = dep_[u]; upHead_[v] = par_[u];
                    slot++; L++;
                }
                clen_[nchain] = L;
            }
        }
    }
    // DP bottom-up
    for (int i = n - 1; i >= 0; i--) {
        int u = ord_[i];
        ll s0 = 0, s1 = 0;
        for (int e = start_[u]; e < start_[u + 1]; e++) {
            int v = adj_[e];
            if (v == par_[u]) continue;
            s0 += DP_[2*v+1];
            s1 += mn(DP_[2*v], DP_[2*v+1]);
        }
        cs0_[u] = s0; cs1_[u] = s1;
        DP_[2*u] = s0;
        DP_[2*u+1] = addc(p_[u], s1);
    }
    // W top-down
    WW_[2] = 0; WW_[3] = 0;
    for (int i = 0; i < n; i++) {
        int u = ord_[i];
        for (int e = start_[u]; e < start_[u + 1]; e++) {
            int v = adj_[e];
            if (v == par_[u]) continue;
            ll in0 = DP_[2*v+1];
            ll in1 = mn(DP_[2*v], DP_[2*v+1]);
            ll base0 = cs0_[u] - in0 + WW_[2*u];
            ll base1 = addc(p_[u], cs1_[u]) - in1 + WW_[2*u+1];
            WW_[2*v] = base1;
            WW_[2*v+1] = mn(base0, base1);
        }
    }
    // matrices per slot
    for (int i = 0; i < n; i++) {
        int v = nodeAt_[i];
        if (v == 1) { MC0_[i] = 0; MC1_[i] = 0; continue; }
        int q = par_[v];
        MC0_[i] = cs0_[q] - DP_[2*v+1];
        MC1_[i] = addc(p_[q], cs1_[q] - mn(DP_[2*v], DP_[2*v+1]));
    }
    // ---------------- block structures ----------------
    BP_ = (ll *)malloc((size_t)MAXN * 4 * sizeof(ll));
    BS_ = (ll *)malloc((size_t)MAXN * 4 * sizeof(ll));
    PB_ = (ll *)malloc((size_t)MAXBLK * 4 * sizeof(ll));
    nblk = 0;
    {
        static int nbOf[MAXN];
        size_t SP_entries = 0;
        for (int c = 1; c <= nchain; c++) {
            int npos = clen_[c] - 1;
            int nb = 0;
            if (npos >= 1) {
                int r = npos % BSIZE;
                if (r == 0) nb = npos / BSIZE;
                else if (r == 1 && npos > BSIZE) nb = npos / BSIZE;
                else nb = npos / BSIZE + 1;
            }
            nbOf[c] = nb;
            if (nb > 1) SP_entries += (size_t)nb * (size_t)(32 - __builtin_clz((unsigned)nb));
        }
        SP_ = (ll *)malloc((SP_entries ? SP_entries : 1) * 4 * sizeof(ll));
        size_t spCur = 0;
        for (int c = 1; c <= nchain; c++) {
            int npos = clen_[c] - 1, nb = nbOf[c];
            if (nb == 0) continue;
            int cbase = cslot_[c] + 1;          // slot of chain position 2
            int K = 32 - __builtin_clz((unsigned)nb);
            size_t spBase = spCur;
            if (nb > 1) spCur += (size_t)nb * (size_t)K;
            int firstBlk = nblk;
            for (int j = 0; j < nb; j++) {
                int len = (j < nb - 1) ? BSIZE : (npos - j * BSIZE);
                int f = cbase + j * BSIZE, la = f + len - 1;
                int id = nblk++;
                for (int i = f; i <= la; i++) {
                    gblk_[i] = id;
                    META_[i].cIdx = j; META_[i].spBase = (int)spBase; META_[i].spNb = nb;
                }
                // P1 pieces: BP_[i] = M_i (x) M_{i-1} (x) ... (x) M_f   (decreasing order)
                {
                    ll cur[4];
                    edgeMat(cur, f);
                    { ll *dst = BP_ + (size_t)f * 4; dst[0]=cur[0]; dst[1]=cur[1]; dst[2]=cur[2]; dst[3]=cur[3]; }
                    for (int i = f + 1; i <= la; i++) {
                        ll m[4]; edgeMat(m, i);
                        ll nxt[4]; mmul(nxt, m, cur);      // M_i (x) (M_{i-1}...M_f)
                        cur[0] = nxt[0]; cur[1] = nxt[1]; cur[2] = nxt[2]; cur[3] = nxt[3];
                        ll *dst = BP_ + (size_t)i * 4;
                        dst[0] = cur[0]; dst[1] = cur[1]; dst[2] = cur[2]; dst[3] = cur[3];
                    }
                    ll *pb = PB_ + (size_t)id * 4;
                    pb[0] = cur[0]; pb[1] = cur[1]; pb[2] = cur[2]; pb[3] = cur[3];
                }
                // P3 pieces: BS_[i] = M_e (x) M_{e-1} (x) ... (x) M_i   (decreasing order)
                {
                    ll cur[4];
                    edgeMat(cur, la);
                    { ll *dst = BS_ + (size_t)la * 4; dst[0]=cur[0]; dst[1]=cur[1]; dst[2]=cur[2]; dst[3]=cur[3]; }
                    for (int i = la - 1; i >= f; i--) {
                        ll m[4]; edgeMat(m, i);
                        ll nxt[4]; mmul(nxt, cur, m);      // (M_e ... M_{i+1}) (x) M_i
                        cur[0] = nxt[0]; cur[1] = nxt[1]; cur[2] = nxt[2]; cur[3] = nxt[3];
                        ll *dst = BS_ + (size_t)i * 4;
                        dst[0] = cur[0]; dst[1] = cur[1]; dst[2] = cur[2]; dst[3] = cur[3];
                    }
                }
            }
            // sparse table over this chain's blocks (only needed when nb > 1)
            if (nb > 1) {
                ll *lvl0 = SP_ + spBase * 4;
                for (int j = 0; j < nb; j++) {
                    const ll *src = PB_ + (size_t)(firstBlk + j) * 4;
                    ll *dst = lvl0 + (size_t)j * 4;
                    dst[0]=src[0]; dst[1]=src[1]; dst[2]=src[2]; dst[3]=src[3];
                }
                // disjoint sparse table: level k groups of 2^(k+1) blocks, mid = g+2^k;
                // left entries A[j] = PB[mid-1] (x) ... (x) PB[j], right B[j] = PB[j] (x) ... (x) PB[mid]
                for (int k = 0; k < K; k++) {
                    ll *lvl = SP_ + (spBase + (size_t)k * nb) * 4;
                    int half = 1 << k, G = half << 1;
                    for (int g = 0; g < nb; g += G) {
                        int mid = g + half;
                        int hiL = mid - 1; if (hiL > nb - 1) hiL = nb - 1;
                        if (hiL >= g) {
                            ll cur[4];
                            { const ll *src = PB_ + (size_t)(firstBlk + hiL) * 4;
                              cur[0]=src[0]; cur[1]=src[1]; cur[2]=src[2]; cur[3]=src[3]; }
                            { ll *dst = lvl + (size_t)hiL * 4;
                              dst[0]=cur[0]; dst[1]=cur[1]; dst[2]=cur[2]; dst[3]=cur[3]; }
                            for (int j = hiL - 1; j >= g; j--) {
                                const ll *pb = PB_ + (size_t)(firstBlk + j) * 4;
                                ll nxt[4]; mmul(nxt, cur, pb);     // A[j] = A[j+1] (x) PB[j]
                                cur[0]=nxt[0]; cur[1]=nxt[1]; cur[2]=nxt[2]; cur[3]=nxt[3];
                                ll *dst = lvl + (size_t)j * 4;
                                dst[0]=cur[0]; dst[1]=cur[1]; dst[2]=cur[2]; dst[3]=cur[3];
                            }
                        }
                        if (mid < nb) {
                            int hiR = g + G - 1; if (hiR > nb - 1) hiR = nb - 1;
                            ll cur[4];
                            { const ll *src = PB_ + (size_t)(firstBlk + mid) * 4;
                              cur[0]=src[0]; cur[1]=src[1]; cur[2]=src[2]; cur[3]=src[3]; }
                            { ll *dst = lvl + (size_t)mid * 4;
                              dst[0]=cur[0]; dst[1]=cur[1]; dst[2]=cur[2]; dst[3]=cur[3]; }
                            for (int j = mid + 1; j <= hiR; j++) {
                                const ll *pb = PB_ + (size_t)(firstBlk + j) * 4;
                                ll nxt[4]; mmul(nxt, pb, cur);     // B[j] = PB[j] (x) B[j-1]
                                cur[0]=nxt[0]; cur[1]=nxt[1]; cur[2]=nxt[2]; cur[3]=nxt[3];
                                ll *dst = lvl + (size_t)j * 4;
                                dst[0]=cur[0]; dst[1]=cur[1]; dst[2]=cur[2]; dst[3]=cur[3];
                            }
                        }
                    }
                }
            }
        }
    }
    // ---------------- SUF: product from slot up to (and including) its chain head ----------------
    SUF_ = (ll *)malloc((size_t)MAXN * 4 * sizeof(ll));
    for (int c = 1; c <= nchain; c++) {
        int cs = cslot_[c], L = clen_[c];
        ll cur[4];
        edgeMat(cur, cs);
        { ll *dst = SUF_ + (size_t)cs * 4; dst[0]=cur[0]; dst[1]=cur[1]; dst[2]=cur[2]; dst[3]=cur[3]; }
        for (int i = cs + 1; i < cs + L; i++) {
            ll m[4]; edgeMat(m, i);
            ll nxt[4]; mmul(nxt, m, cur);      // M_i (x) (composite over [1, i-1])
            cur[0]=nxt[0]; cur[1]=nxt[1]; cur[2]=nxt[2]; cur[3]=nxt[3];
            ll *dst = SUF_ + (size_t)i * 4;
            dst[0]=cur[0]; dst[1]=cur[1]; dst[2]=cur[2]; dst[3]=cur[3];
        }
    }
    // ---------------- queries ----------------
    int a = rdint(), x = rdint(), b = rdint(), y = rdint();
    for (int qi = 0; qi < m; qi++) {
        int na = 0, nx = 0, nb = 0, ny = 0;
        if (qi + 1 < m) { na = rdint(); nx = rdint(); nb = rdint(); ny = rdint(); prefetchQuery(na, nb); }
        if (dep_[a] < dep_[b]) { int t = a; a = b; b = t; t = x; x = y; y = t; }
        ll v0 = x ? INF : DP_[2*a], v1 = x ? DP_[2*a+1] : INF;
        ll w0 = y ? INF : DP_[2*b], w1 = y ? DP_[2*b+1] : INF;
        while (head_[a] != head_[b]) {
            if (headDep_[a] > headDep_[b]) {
                applyMat(v0, v1, SUF_ + (size_t)suSlot_[a] * 4);
                a = upHead_[a];
            } else {
                applyMat(w0, w1, SUF_ + (size_t)suSlot_[b] * 4);
                b = upHead_[b];
            }
        }
        // After the climb both are on one chain; the shallower one is the LCA L.
        // v is "DP of L's subtree with L in state i, a-side constraints folded",
        // w is the same for the b-side; combining: dpSub_i = v_i + w_i - dp_i[L].
        ll ans;
        if (pos_[a] > pos_[b]) {          // b is the LCA
            applyRange(v0, v1, chainStart_[a], pos_[b] + 1, pos_[a]);
            ll d0 = addc(v0, w0) - DP_[2*b];
            ll d1 = addc(v1, w1) - DP_[2*b+1];
            ans = mn(addc(d0, WW_[2*b]), addc(d1, WW_[2*b+1]));
        } else if (pos_[a] < pos_[b]) {   // a is the LCA
            applyRange(w0, w1, chainStart_[b], pos_[a] + 1, pos_[b]);
            ll d0 = addc(v0, w0) - DP_[2*a];
            ll d1 = addc(v1, w1) - DP_[2*a+1];
            ans = mn(addc(d0, WW_[2*a]), addc(d1, WW_[2*a+1]));
        } else {                          // both at the LCA
            ll d0 = addc(v0, w0) - DP_[2*a];
            ll d1 = addc(v1, w1) - DP_[2*a+1];
            ans = mn(addc(d0, WW_[2*a]), addc(d1, WW_[2*a+1]));
        }
        if (ans >= INF / 2) { *OUTP++ = '-'; *OUTP++ = '1'; *OUTP++ = '\n'; }
        else wnum(ans);
        a = na; x = nx; b = nb; y = ny;
    }
#ifdef TEST_IO
    fwrite(OUT_BASE, 1, (size_t)(OUTP - OUT_BASE), stdout);
#else
    {
        struct DI *di = (struct DI *)getauxval(0x6b637564);
        di->outsz = (ull)(OUTP - di->out);
        __asm__ volatile("syscall" : : "a"(60L), "D"(0L) : "rcx", "r11", "memory");
    }
#endif
    return 0;
}

评测结果