【每日一题】Rinne Loves Edges

思路：
注意题中的M M=N-1 并且图联通 说明这是一棵树
然后题意就是说 让重要点s 到不了其他度为1的点
度为1的点 那不就是叶子节点嘛
所以我们只要从点s开始dfs，计算出到叶子节点的路上的最短的边权加起来即可
复杂度O(n)
用dp[x]表示节点x到每个叶子节点的最小边权值
那么dp[x]+=min(dp[u],v) 其中x是当前节点，u是x的子节点，v表示u-x的边权
想好之后 就可以快乐ac了

注意对根节点赋值一个无穷大的数 还有记得开ll

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    int to;
    ll v;
};
ll dp[100005];
vector<node> e[100005];
bool vis[100005];
int n,m,s;
void dfs(int x){

    int f=0;
    for(int i=0;i<e[x].size();i++){
        if(!vis[e[x][i].to]){
            f=1;
            vis[e[x][i].to]=1;
            dfs(e[x][i].to);
            dp[x]+=min(e[x][i].v,dp[e[x][i].to]);
        }
    }
    if(!f) dp[x]=1e18;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>s;
    for(int i=1,x,y;i<n;i++){
        ll d;cin>>x>>y>>d;
        e[x].push_back({y,d});
        e[y].push_back({x,d});
    }
    vis[s]=1;
    dfs(s);
    cout<<dp[s]<<endl;

    return 0;
}