题目大意：

Rinne 一个 n 个节点 m 条边的无向连通图，每条边有一个边权 wi 选取一个 点 S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。问删除这些边的最小代价。

题解

由于m = n-1,所以该图是一棵树，以s为根节点，先找到度为一的 叶子 节点， 然后向上递推，递推过程如下。
设 dp[u] 表示u节点的子树中所有度为1的点都已经不与s节点在同一连通块内的最小代价。
dp[u] += min(dp[j], edge[j][u].w)（j是u的子节点）不切连接u和j的边的最小代价就是dp[j]， 而切的最小代价是edge[j][u].w，即边权。
还有要注意的是，对于叶子节点来说，dp[叶子]初始化为inf

代码

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

const int N = 1e5 + 50;

struct Edge{int to; ll w;};
vector<Edge>G[N];
int n,m,s;
ll cost[N];

void dfs(int rt, int fa)
{
    if(G[rt].size() == 1 && rt != s) {cost[rt] = INT_MAX; return;}

    for (int i = 0; i < G[rt].size(); i ++)
    {
        Edge v = G[rt][i];
        if(v.to == fa) continue;
        dfs(v.to, rt);
        cost[rt] += min(v.w, cost[v.to]);
    }

}
int main()
{
    scanf("%d%d%d",&n, &m, &s);
    for(int i=1;i<=m;i++){
        int u,v; ll w; scanf("%d%d%lld",&u, &v, &w);
        G[u].push_back(Edge{v,w});
        G[v].push_back(Edge{u,w});
    }
    dfs(s, 0);
    cout << cost[s];
}