题目

Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。
她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 w_i 现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。
定义删除一条边的代价为这条边的边权，现在 Rinne 想知道完成这个游戏的最小的代价，这样她就能轻松到达 rk1 了！作为回报，她会让你的排名上升一定的数量。
2≤S≤N≤10^5,M=N−1，保证答案在 C++ long long 范围内。

做法

代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
const int inf = 0x3f3f3f3f;
int n, m, s, val[N], mrk[N];
vector<pair<int,int> > g[N];
ll dp[N];
void dfs(int u, int p){
    if (g[u].size() == 1 && u != s) dp[u] = inf;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i].first;
        ll w = g[u][i].second;
        if (v == p) continue;
        dfs(v, u);
        dp[u] += min(dp[v], w);
    }
}
int main(void){
    IOS;
    cin >> n >> m >> s;
    for (int i = 0; i < m; ++i){
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    dfs(s, s);
    cout << dp[s] << endl;
    return 0;
}