思路与算法

先求无约束的最小带权顶点覆盖：f[u][0]是u不选，等于所有孩子f[v][1]之和；f[u][1]是p[u]加上各孩子两个状态的较小值。从路径孩子v向父亲u传播一个受限二状态向量时，先从f[u]中减掉v的原贡献，再加入v的新贡献；该操作是2×2的min-plus线性转移。按倍增合成这些转移并同时保存祖先。每个询问把两个指定结点的禁用状态设为INF，提升较深的结点；如果两个限制在同一祖先链，合并状态限制后向根提升。否则提升至LCA的两个不同孩子，在LCA同时替换这两个孩子的贡献，再把结果提升到根。

正确性说明

树形DP的两个状态完整区分了每条父子边由哪个端点覆盖，子树之间在根状态固定后独立。替换孩子贡献的转移只改变受限制子树，其余孩子仍可采用各自最优方案，故向父亲传播精确。min-plus转移的合成保持连续父子传播的最优费用，倍增与逐层计算等价。两个被限制子树在LCA以下不相交，因此在LCA同时扣除原贡献并加入新贡献不会漏算或重复；祖先重合的情况直接叠加禁止状态。根两个状态的最小值就是该独立询问的最优费用，均不可行则输出-1。

复杂度

邻接表、树形DP及所有向量初始化为O(n)，祖先及二状态转移表为O(n log n)时间和空间。每次询问执行O(log n)次常数规模转移，合计O((n+m)log n)时间、O(n log n)空间。不为每次询问复制或清空整棵树。

易错点

同一询问的a和b不同，但其中一个可以是另一个的祖先。原始f有限，扣贡献时只能扣原始有限费用，不能对INF做减法。INF取大于所有合法费用之和且相加不溢出的值；32位费用总和不足以覆盖300000×100000。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 100000000000000000LL;
struct Mat {
    ll a[2][2];
};
Mat mul(const Mat &a, const Mat &b) {
    Mat c;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            c.a[i][j] = min(INF, min(a.a[i][0] + b.a[0][j], a.a[i][1] + b.a[1][j]));
    return c;
}
array<ll, 2> apply(const Mat &a, array<ll, 2> b) {
    return {min(INF, min(a.a[0][0] + b[0], a.a[0][1] + b[1])),
            min(INF, min(a.a[1][0] + b[0], a.a[1][1] + b[1]))};
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    string type;
    if (!(cin >> n >> q >> type))
        return 0;
    vector<ll> p(n);
    for (auto &x : p)
        cin >> x;
    vector<vector<int>> g(n);
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int LOG = 1;
    while ((1 << LOG) <= n)
        LOG++;
    vector<int> par(n, -1), dep(n), ord(1, 0);
    for (size_t k = 0; k < ord.size(); k++) {
        int u = ord[k];
        for (int v : g[u])
            if (v != par[u]) {
                par[v] = u;
                dep[v] = dep[u] + 1;
                ord.push_back(v);
            }
    }
    vector<array<ll, 2>> f(n);
    for (int k = n - 1; k >= 0; k--) {
        int u = ord[k];
        f[u] = {0, p[u]};
        for (int v : g[u])
            if (par[v] == u) {
                f[u][0] += f[v][1];
                f[u][1] += min(f[v][0], f[v][1]);
            }
    }
    vector<vector<int>> up(LOG, vector<int>(n));
    vector<vector<Mat>> mt(LOG, vector<Mat>(n));
    for (int u = 0; u < n; u++) {
        int v = par[u];
        up[0][u] = v < 0 ? 0 : v;
        if (v < 0)
            mt[0][u] = {{{0, INF}, {INF, 0}}};
        else {
            ll x = f[v][1] - min(f[u][0], f[u][1]);
            mt[0][u] = {{{INF, f[v][0] - f[u][1]}, {x, x}}};
        }
    }
    for (int j = 1; j < LOG; j++)
        for (int u = 0; u < n; u++) {
            int v = up[j - 1][u];
            up[j][u] = up[j - 1][v];
            mt[j][u] = mul(mt[j - 1][v], mt[j - 1][u]);
        }
    auto lift = [&](int &u, array<ll, 2> &v, int d) {
        for (int j = 0; j < LOG; j++)
            if ((d >> j) & 1) {
                v = apply(mt[j][u], v);
                u = up[j][u];
            }
    };
    while (q--) {
        int a, x, b, y;
        cin >> a >> x >> b >> y;
        --a;
        --b;
        auto va = f[a], vb = f[b];
        va[1 - x] = INF;
        vb[1 - y] = INF;
        if (dep[a] < dep[b]) {
            swap(a, b);
            swap(x, y);
            swap(va, vb);
        }
        lift(a, va, dep[a] - dep[b]);
        array<ll, 2> ans;
        int u;
        if (a == b) {
            va[1 - y] = INF;
            ans = va;
            u = a;
        } else {
            for (int j = LOG - 1; j >= 0; j--)
                if (up[j][a] != up[j][b]) {
                    va = apply(mt[j][a], va);
                    vb = apply(mt[j][b], vb);
                    a = up[j][a];
                    b = up[j][b];
                }
            u = par[a];
            ans[0] = min(INF, f[u][0] - f[a][1] - f[b][1] + va[1] + vb[1]);
            ans[1] = min(INF, f[u][1] - min(f[a][0], f[a][1]) - min(f[b][0], f[b][1]) +
                                  min(va[0], va[1]) + min(vb[0], vb[1]));
        }
        lift(u, ans, dep[u]);
        ll z = min(ans[0], ans[1]);
        cout << (z >= INF ? -1 : z) << '\n';
    }
}