Rinne Loves Edges

题意

有一颗树，可以删去一些边，代价是边权。

现在要使得叶子节点和根节点不连通，求删边的最小代价。

分析

M=N−1，这也太坑了吧。

举个栗子

我们可以选择删去这条边，或者删去和这条边，显然选代价小的。

我们可以通过求出所需的代价。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 101110;
const int M = 1e9+7;
int n,m,s,ans;

vector<pii> v[maxn];

int dfs(int u,int pre,int res)        //res表示u和pre边的代价
{   
    int tmp = 0;                //tmp表示删除全部子树的最小代价
    for(auto i : v[u])
    {
        if(i.first == pre) continue;
        tmp += dfs(i.first,u,i.second);
    }
    if(tmp == 0) tmp = res;
    //if(u == 1) cout<<tmp<<' '<<res<<endl;
    return min(tmp,res);
}


signed main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    for(int i = 1,x,y,z; i <= m; i++) 
    {
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    cout<<dfs(s,0,1e18)<<endl;
    return 0;
}