原题链接：

https://ac.nowcoder.com/acm/problem/22598

题目大意：

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

解题思路：

树形，记录删除节点i下面的一些边使叶子节点到不了根节点的最小权值。递推公式为：

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef complex <double> cp;
#define debug(a) cout<<#a<<":"<<a<<endl;
#define fr freopen("in.txt","r",stdin);
#define Fill(x,a) memset(x,a,sizeof(x))
#define cpy(a,b) memcpy(a,b,sizeof(a))
const double PI = acos(-1);
const ll INF=0x3f3f3f3f;
const ll N=1e6+7;
const ll mod=1e9+7;
ll maxn,minn;
ll T,n,m,q,s;

ll dp[N];
ll head[N];
ll cnt;
struct aa{
    ll u,w,next;
}edge[N];

void init(){
    cnt=1;
    Fill(dp,0);
    Fill(head,0);
    return ;
}

void add(ll u,ll v,ll w){
    edge[cnt].u=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    return ;
}

void dfs(ll u,ll p){
    ll v,w;
    ll a=0;
    if(edge[head[u]].next==0&&u!=s){
        dp[u]=INF;
        return ;
    }
    for(ll i=head[u];i!=0;i=edge[i].next){
        v=edge[i].u;
        w=edge[i].w;
        if(v==p)    continue;
        dfs(v,u);
        dp[u]=dp[u]+min(dp[v],w);
    }
    return ;
}

int main(){
    ll u,w,v;
    init();
    cin>>n>>m>>s;
    for(ll i=1;i<=m;i++){
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }

    dfs(s,0);
    cout<<dp[s]<<endl;

    return 0;
}