题解 | #Rinne Loves Edges#

问题分析

1. 拓扑结构

题目指出该图包含 个节点和 个边，且 。在保证图连通的前提下，该拓扑结构本质上是一棵树。

2. 目标归纳

任务是选取 作为根节点，通过删除边（支付代价）使得所有除 以外的度为 1 的节点（即树的叶子节点）无法到达 。这实际上是一个树上的最小剪切（Minimum Cut）问题。

3. 核心约束

• 根节点 ：作为隔离的中心，不可移动。
• 目标节点：所有原始树结构的叶子节点（除非叶子本身就是 ）。
• 最小化代价：边权即为剪断该路径的成本。

算法：树形动态规划 (Tree DP)

对于树状结构的最小成本/最优路径问题，树形递归 DP 是最优选择。由于每一棵子树的隔离状态仅取决于其根节点与子节点之间的连接，具有典型的最优子结构和无后效性。

1. 状态定义

设 表示：以 为根的子树中，所有叶子节点到 的路径均已被切断的最小代价。

2. 转移逻辑分析

对于当前节点 及其子节点 ，要使 及其子树中的叶子无法到达 ，存在两种策略：

1. 直接切断边 ：代价为该边的权值 。
2. 保留边 ，但切断 内部所有叶子到 的路径：代价为 。

对于子节点 ，这两者取其小：。

3. 状态转移方程

4. 边界条件（Base Case）

• 叶子节点（且不为 ）：由于叶子节点本身就是目标，无法在内部切断。为了让父节点强制考虑切断 这条边，我们将叶子节点的 值初始化为无穷大 ()。
• 非叶子节点：初始化 ，然后累加各子树的结果。

复杂度分析

1. 时间复杂度

• 建树阶段：采用邻接表存储，复杂度为 。
• 遍历阶段：采用一次深度优先搜索（DFS），每个节点和每条边仅被访问一次。
• 总复杂度：。

2. 空间复杂度

• 存储开销：邻接表维护 个顶点和 条边，空间为 。
• 递归开销：DFS 递归深度在最坏情况下（树退化为链）为 。
• 总复杂度：。

代码实现

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, ll>;

static constexpr ll INF = 2e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    cin >> n >> m >> s;

    vector<vector<pii>> g(n + 1);
    vector<int> deg(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        deg[u]++;
        deg[v]++;
    }

    auto dfs = [&](auto&& self, int u, int p) -> ll {
        if (u != s && deg[u] == 1) {
            return INF;
        }
        ll total = 0;
        for (auto [v, w] : g[u]) {
            if (v == p)
                continue;
            total += min(w, self(self, v, u));
        }
        return total;
    };

    cout << dfs(dfs, s, -1) << endl;
}