算法标签

$树形DP$、$LCA$、$倍增预处理$、$换根DP$、$查询路径计算$

问题核心

给定一棵有$n$座城市、$n-1$条道路的树，城市$i$驻军花费为$p_i$，约束是$相邻城市至少一座驻军$。$m$个查询指定$a$（$x=0/1$：不驻/必驻）和$b$（$y=0/1$：不驻/必驻），求满足查询和约束的最小花费，不可行则输出$-1$。

核心思路

1. 子树DP（$dfs1$）：自底向上算每个节点子树的最小花费，得到$d[x][0]$（$x$驻）和$d[x][1]$（$x$不驻）。
2. 换根DP（$dfs2$）：自顶向下算每个节点父树的最小花费，得到$u[x][0]$（$x$驻）和$u[x][1]$（$x$不驻）。
3. 倍增预处理（$prep$）：构建$g$数组，支持$O(\log n)$查询节点向上路径的花费。
4. 查询处理（$calc$）：用$LCA$找公共祖先，分情况整合子树、父树、路径花费，得到最小总花费。

代码关键解析

• $dfs1$：子树DP，基础花费计算，支撑后续换根。
• $dfs2$：换根DP，扩展到全树任意节点为根的花费。
• $prep$：倍增预处理，加速路径花费查询。
• $LCA$：找两节点最近公共祖先，拆分查询路径。
• $calc$：核心查询逻辑，整合各部分花费，判断可行性。

复杂度分析

• 时间：$O(n\log n + m\log n)$，适配$n=m\le1e5$。
• 空间：$O(n\log n)$，存储倍增和DP数组。

关键注意点

1. 状态一致性：$d$和$u$数组的“驻/不驻”定义需统一。
2. 去重花费：计算总花费时，剔除$LCA$或根节点的重复$p$值。
3. 不可行标记：用$INF$标记违反约束的状态，避免误判。

带详细注解的代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;
const int N = 200005;

int n, m, hd[N], to[N * 2], nx[N * 2], ec;
int fa[N][21], dep[N];
ll p[N], d[N][2], u[N][2], g[N][21][2][2];

void add(int u, int v) {
    to[++ec] = v;
    nx[ec] = hd[u];
    hd[u] = ec;
}

void dfs1(int x, int f) {
    fa[x][0] = f;
    dep[x] = dep[f] + 1;
    d[x][0] = p[x];
    d[x][1] = 0;

    for (int e = hd[x]; e; e = nx[e]) {
        int v = to[e];

        if (v == f)
            continue;

        dfs1(v, x);
        d[x][0] += min(d[v][0], d[v][1]);
        d[x][1] += d[v][0];
    }
}

void dfs2(int x, int f) {
    for (int e = hd[x]; e; e = nx[e]) {
        int v = to[e];

        if (v == f)
            continue;

        ll b0 = d[x][0] - min(d[v][0], d[v][1]) - p[x];
        ll b1 = d[x][1] - d[v][0];
        u[v][0] = min(b0 + u[x][0], b1 + u[x][1]) + p[v];
        u[v][1] = b0 + u[x][0];
        dfs2(v, x);
    }
}

void prep() {
    for (int i = 1; i <= n; i++) {
        g[i][0][0][0] = d[fa[i][0]][0] - min(d[i][0], d[i][1]);
        g[i][0][1][0] = g[i][0][0][0];
        g[i][0][0][1] = d[fa[i][0]][1] - d[i][0];
        g[i][0][1][1] = INF;
    }

    for (int j = 1; j <= 20; j++)
        for (int i = 1; i <= n; i++) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];

            for (int x = 0; x < 2; x++)
                for (int y = 0; y < 2; y++) {
                    ll a = g[i][j - 1][x][0] + g[fa[i][j - 1]][j - 1][0][y];
                    ll b = g[i][j - 1][x][1] + g[fa[i][j - 1]][j - 1][1][y];
                    g[i][j][x][y] = min(a, b);
                }
        }
}

ll up(int x, int y, int sx, int sy) {
    ll r0 = 0, r1 = 0;
    bool fst = 1;

    for (int i = 20; i >= 0; i--)
        if (dep[fa[x][i]] >= dep[y]) {
            if (fst) {
                fst = 0;
                r0 = g[x][i][sx][0];
                r1 = g[x][i][sx][1];
            } else {
                ll t0 = r0, t1 = r1;
                r0 = min(t0 + g[x][i][0][0], t1 + g[x][i][1][0]);
                r1 = min(t0 + g[x][i][0][1], t1 + g[x][i][1][1]);
            }

            x = fa[x][i];
        }

    return sy == 0 ? r0 : r1;
}

int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);

    for (int i = 20; i >= 0; i--)
        if (dep[fa[x][i]] >= dep[y])
            x = fa[x][i];

    if (x == y)
        return x;

    for (int i = 20; i >= 0; i--)
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }

    return fa[x][0];
}

ll calc(int a, int da, int b, int db) {
    if (dep[a] < dep[b]) {
        swap(a, b);
        swap(da, db);
    }

    int c = lca(a, b);
    da ^= 1;
    db ^= 1;

    if (c == b) {
        ll ans = d[a][da] + u[b][db] + up(a, b, da, db);

        if (db == 0)
            ans -= p[b];

        return ans >= INF ? -1 : ans;
    } else {
        ll res = INF;

        for (int s = 0; s < 2; s++) {
            ll t = d[a][da] + d[b][db] + up(a, c, da, s) + up(b, c, db, s) + u[c][s] - d[c][s];

            if (s == 0)
                t -= p[c];

            res = min(res, t);
        }

        return res >= INF ? -1 : res;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string tp;
    cin >> n >> m >> tp;

    for (int i = 1; i <= n; i++)
        cin >> p[i];

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }

    dfs1(1, 0);
    u[1][0] = p[1];
    u[1][1] = 0;
    dfs2(1, 0);
    prep();

    while (m--) {
        int a, da, b, db;
        cin >> a >> da >> b >> db;
        cout << calc(a, da, b, db) << "\n";
    }

    return 0;
}