代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000, lgn = 17;
const ll inf = 1e18;
int n, q;
ll w[maxn + 10];
ll f[maxn + 10][2], g[maxn + 10][2];

struct edge {
    int to, nxt;
}eg[maxn * 2 + 10];
int h[maxn + 10], egcnt;

void add(int &h, int to) {
    eg[++egcnt] = (edge){to, h};
    h = egcnt;
}

void dpdn(int p, int fa) {
    f[p][1] = w[p];
    for (int i = h[p]; i; i = eg[i].nxt) {
        int e = eg[i].to;
        if (e != fa) {
            dpdn(e, p);
            f[p][0] += f[e][1];
            f[p][1] += min(f[e][0], f[e][1]);
        }
    }
}

void dpup(int p, int fa) {
    for (int i = h[p]; i; i = eg[i].nxt) {
        int e = eg[i].to;
        if (e != fa) {
            g[e][0] = g[p][1] + f[p][1] - min(f[e][0], f[e][1]);
            g[e][1] = min(g[e][0], g[p][0] + f[p][0] - f[e][1]);
            dpup(e, p);
        }
    }
}
struct data {
    ll f[2][2];
    
};
data operator + (const data &a, const data &b) {
    data ans;
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j) ans.f[i][j] = inf;
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            if (i || j)
                for (int k = 0; k < 2; ++k)
                    for (int l = 0; l < 2; ++l)
                        ans.f[k][l] = min(ans.f[k][l], a.f[k][i] + b.f[j][l]);
    return ans;
}
int ff[maxn + 10][lgn + 1], dep[maxn + 10];
data gg[maxn + 10][lgn + 1];

void dpjump(int p) {
    dep[p] = dep[ff[p][0]] + 1;
    for (int i = 1; i <= lgn; ++i) {
        ff[p][i] = ff[ff[p][i - 1]][i - 1];
        gg[p][i] = gg[p][i - 1] + gg[ff[p][i - 1]][i - 1];
    }
    for (int i  = h[p]; i; i = eg[i].nxt) {
        int e = eg[i].to;
        if (e != ff[p][0]) {
            ff[e][0] = p;
            gg[e][0].f[0][1] = gg[e][0].f[1][0] = inf;
            gg[e][0].f[0][0] = f[p][0] - f[e][1];
            gg[e][0].f[1][1] = f[p][1] - min(f[e][0], f[e][1]);
            dpjump(e);
        }
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = lgn, t = dep[x] - dep[y]; i >= 0; --i)
        if (t >> i & 1) x = ff[x][i];
    if (x == y) return x;
    for (int i = lgn; i >= 0; --i)
        if (ff[x][i] != ff[y][i]) {
            x = ff[x][i]; y = ff[y][i];
        }
    return ff[x][0];
}

int main() {
    scanf("%d%d", &n, &q); scanf("%*s");
    for (int i = 1; i <= n; ++i) scanf("%lld", &w[i]);
    for (int i = 1; i < n; ++i) {
        int l, r; scanf("%d%d", &l, &r);
        add(h[l], r); add(h[r], l);
    }
    dpdn(1, 0);
    dpup(1, 0);
    dpjump(1);
    while (q--) {
        int x, a, y, b; scanf("%d%d%d%d", &x, &a, &y, &b);
        if (dep[x] < dep[y]) swap(x, y), swap(a, b);
        data ans, tmp, ans2; 
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                if (j == a) ans.f[i][j] = f[x][j];
                else ans.f[i][j] = inf;
        int p = lca(x, y);
        for (int i = lgn, t = dep[x] - dep[p] - 1; i >= 0; --i)
            if (t >> i & 1) {
                ans = ans + gg[x][i]; x = ff[x][i];
            }
        if (p == y) {
            tmp.f[0][1] = tmp.f[1][0] = inf;
            if (b == 0) tmp.f[0][0] = g[p][0] + f[p][0] - f[x][1];
            else tmp.f[0][0] = inf;
            if (b == 1) tmp.f[1][1] = g[p][1] + f[p][1] - min(f[x][0], f[x][1]);
            else tmp.f[1][1] = inf;
            ans = ans + tmp;
        } else {
            for (int i = 0; i < 2; ++i)
                for (int j = 0; j < 2; ++j)
                    if (j == b) ans2.f[i][j] = f[y][j];
                    else ans2.f[i][j] = inf;
            for (int i = lgn, t = dep[y] - dep[p] - 1; i >= 0; --i)
                if (t >> i & 1) {
                    ans2 = ans2 + gg[y][i]; y = ff[y][i];
                }
            swap(ans2.f[0][1], ans2.f[1][0]);
            tmp.f[0][1] = tmp.f[1][0] = inf;
            tmp.f[0][0] = g[p][0] + f[p][0] - f[x][1] - f[y][1];
            tmp.f[1][1] = g[p][1] + f[p][1] - min(f[x][0], f[x][1]) - min(f[y][0], f[y][1]);
            ans = ans + tmp + ans2;
        }
        ll res = inf;
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j) res = min(res, ans.f[i][j]);
        printf("%lld\n", res >= inf ? -1 : res);
    }
}

评测结果