1 条题解

  • 0
    @ 2026-11-12 21:04:50

    T2 皇宫守卫(guard)题解

    题意简述

    给定一棵 nn 个点的树,点 ii 放守卫的代价为 cic_i。一个守卫能覆盖自己以及与它相邻的所有点。求覆盖所有点的最小总代价。

    思路

    这是树上的最小权支配集问题。以 11 号点为根,对每个点 uu 设计三个状态:

    • dpu,0dp_{u,0}:在 uu 放守卫,覆盖以 uu 为根的子树的最小代价;
    • dpu,1dp_{u,1}:不在 uu 放守卫,但 uu 被至少一个儿子上的守卫覆盖;
    • dpu,2dp_{u,2}:不在 uu 放守卫,且 uu 没有被儿子覆盖,等待父亲来覆盖。

    转移

    设 uu 的儿子集合为 S(u)S(u)。

    状态 00: uu 自己放了守卫,因此每个儿子 vv 无论处于哪种状态都能被 uu 覆盖,取三者最小值:

    $$dp_{u,0}=c_u+\sum_{v\in S(u)}\min(dp_{v,0},dp_{v,1},dp_{v,2}).$$

    状态 22: uu 没有守卫,儿子不能指望 uu 来覆盖,所以儿子只能是状态 00 或 11:

    dpu,2=∑v∈S(u)min⁡(dpv,0,dpv,1).dp_{u,2}=\sum_{v\in S(u)}\min(dp_{v,0},dp_{v,1}).

    状态 11: uu 没有守卫,但必须至少有一个儿子放了守卫。先假设每个儿子取 min⁡(dpv,0,dpv,1)\min(dp_{v,0},dp_{v,1}),然后强制某一个儿子从“较优状态”改成状态 00,取增量最小者:

    $$dp_{u,1}=\sum_{v\in S(u)}\min(dp_{v,0},dp_{v,1}) +\min_{v\in S(u)}\left(dp_{v,0}-\min(dp_{v,0},dp_{v,1})\right).$$

    如果 uu 是叶子,则不存在儿子,dpu,1=+∞dp_{u,1}=+\infty。

    答案

    根节点没有父亲,所以不能处于状态 22。答案为

    min⁡(dp1,0,dp1,1).\min(dp_{1,0},dp_{1,1}).

    正确性证明

    对子树大小归纳,证明三个 dpdp 值分别等于对应状态下的最小代价。

    状态 00: uu 有守卫,子树内每个儿子 vv 都被 uu 覆盖,因此 vv 的子树只需自己覆盖自己,vv 可以取任意合法状态 0/1/20/1/2。各儿子子树互相独立,取和即最优。

    状态 22: uu 没有守卫且没有被儿子覆盖,儿子 vv 不能被 uu 覆盖,所以 vv 不能处于状态 22(状态 22 的含义正是等待父亲覆盖)。vv 只能取 00 或 11,取较小值;各儿子独立,故转移正确。

    状态 11: uu 没有守卫,儿子不能取状态 22。先让每个儿子取 min⁡(dpv,0,dpv,1)\min(dp_{v,0},dp_{v,1}),若其中至少一个儿子已经取了状态 00,则 uu 已被覆盖;否则所有儿子都取了状态 11,需要把某个儿子改成状态 00,额外代价为 dpv,0−min⁡(dpv,0,dpv,1)≥0dp_{v,0}-\min(dp_{v,0},dp_{v,1})\ge 0,选最小者即可。因此转移正确。

    根节点: 根没有父亲,状态 22 不合法;状态 0,10,1 都保证根被覆盖。取最小值即为全局最优。

    复杂度

    每个点只被访问常数次,时间 O(n)O(n),空间 O(n)O(n)。

    参考代码(C++)

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    const long long INF = (long long)4e18;
    
    int main() {
        freopen("guard.in", "r", stdin);
        freopen("guard.out", "w", stdout);
    
        int n;
        if (scanf("%d", &n) != 1) return 0;
        vector<long long> c(n + 1);
        for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);
    
        vector<vector<int>> g(n + 1);
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
    
        // 迭代求先序,再倒序做树形 DP,避免递归爆栈
        vector<int> parent(n + 1, 0), order;
        order.reserve(n);
        vector<int> st;
        st.push_back(1);
        parent[1] = -1;
        while (!st.empty()) {
            int u = st.back();
            st.pop_back();
            order.push_back(u);
            for (int v : g[u]) {
                if (v == parent[u]) continue;
                parent[v] = u;
                st.push_back(v);
            }
        }
    
        vector<long long> dp0(n + 1), dp1(n + 1), dp2(n + 1);
        for (int idx = n - 1; idx >= 0; idx--) {
            int u = order[idx];
            long long sum0 = c[u];
            long long sum01 = 0;
            long long bestDelta = INF;
            bool hasChild = false;
    
            for (int v : g[u]) {
                if (v == parent[u]) continue;
                hasChild = true;
                sum0 += min(dp0[v], min(dp1[v], dp2[v]));
                long long m = min(dp0[v], dp1[v]);
                sum01 += m;
                bestDelta = min(bestDelta, dp0[v] - m);
            }
    
            dp0[u] = sum0;
            dp2[u] = sum01;
            dp1[u] = hasChild ? sum01 + bestDelta : INF;
        }
    
        printf("%lld\n", min(dp0[1], dp1[1]));
        return 0;
    }
    

    易错点

    1. 叶子节点的 dpu,1dp_{u,1} 必须是 +∞+\infty:叶子没有儿子,不可能被儿子覆盖。如果误设成 00,会导致根节点“凭空被覆盖”。
    2. 状态 11 必须强制至少一个儿子放守卫:只取 ∑min⁡(dpv,0,dpv,1)\sum\min(dp_{v,0},dp_{v,1}) 会允许所有儿子都不放守卫。
    3. 根节点不能取状态 22:根没有父亲,状态 22 表示等待父亲覆盖,对根不合法。
    4. 链的深度可达 2×1052\times 10^5:递归 DFS 可能爆栈,建议使用迭代写法。
    5. 答案要用 long long:n≤2×105n\le 2\times 10^5,ci≤109c_i\le 10^9,总和可达 2×10142\times 10^{14}。
    6. 状态 00 的儿子可以取状态 22:因为 uu 有守卫,儿子等待父亲覆盖是合法的;不要漏掉这个转移。

    测试点设计

    测试点 设计意图
    1 样例 1,链长为 33,答案为 11
    2 样例 2,菊花,比较“中心”与“所有叶子”
    3 n=1n=1,答案为 c1c_1
    4 n=2n=2,答案为 min⁡(c1,c2)\min(c_1,c_2)
    5 链长 1010,随机代价,检验基本树形 DP
    6 10510^5 个点的菊花,中心代价为 11,答案为 11
    7 10510^5 个点的菊花,中心代价为 10910^9、叶子代价为 11,答案为 9999999999
    8 2×1052\times 10^5 个点的随机树,随机大代价
    9 2×1052\times 10^5 个点的链,随机大代价,检验迭代 DFS 与长链
    10 2×1052\times 10^5 个点的随机树,所有代价为 11,答案为最小支配集大小
    11 2×1052\times 10^5 个点的完全二叉树,随机大代价
    12 “扫帚”形树:长链末端接大量叶子,检验高度数与大深度同时出现
    • 1

    信息

    ID
    7
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    2
    已通过
    2
    上传者