Rinne Loves Edges

题解：
我们可以从这个s结点出发开始遍历，遍历到根节点，把根节点标为正无穷大，回溯的时候dp[x]代表x出发去掉x到往所有叶子的最小值（删除边的最小值）
比如说这样一棵树。
1.我们可以删除1-2，1-5这两条边。
2.也可以删除2-3，2-4，1-5这三条边。

所以我们通过回溯的方法来找出到底是哪种方法更好一些。
对于dp[1]的1-2这条边来说，
我们取最小值到底是it.v（1-2）这条边小一些，还是dp2这两条边比较小一些。

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
struct node{
    ll v,w;
    node(ll x,ll y){v=x,w=y;}
};
vector<node> a[maxn];
int n,m,s;
ll dp[maxn];
void dfs(ll x,ll fa){
    bool flag=false;
    for(auto it : a[x]){
        if(it.v!=fa){
            flag=true;
            dfs(it.v,x);
            dp[x]+=min(it.w,dp[it.v]);
        }
    }
    if(!flag) dp[x]=1e18;
}
int main()
{
    cin>>n>>m>>s;
    for(int i=0;i<m;i++){
        ll u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        a[u].push_back(node(v,w));
        a[v].push_back(node(u,w));
    }
    dfs(s,-1);
    cout<<dp[s]<<endl;
    return 0;
}