这题看起来是一般图，实际上数据写死了 M=N-1，所以就是一棵树。

而我们的目标是：把 S 和“原图里所有度为 1 且不是 S 的点（叶子）”隔开，删边代价最小。

也就是说：在树上把 S 和这些叶子断开，最小割代价是多少。

把树以 S 为根做树形DP。

定义：

  • has[u]：u 的子树里有没有“需要隔离的叶子”
  • f[u]：在不删 u 到父亲这条边的前提下，把 u 子树里所有目标叶子都和 u 断开的最小代价

先看叶子情况：

  • 如果 u 本身是目标叶子（原度数为1且 u!=S），那它和自己不可能在子树内断开，只能靠父边断，所以设 f[u]=INF，has[u]=1。

再看普通点 u：

  • 枚举每个儿子 v，如果 v 子树没有目标叶子，跳过
  • 如果有，就两种选择：
    1. 直接删 u-v，花 w
    2. 不删 u-v，那就得在 v 子树内部处理，花 f[v]
  • 这条分支取 min(w,f[v])
  • 全部儿子分支求和，就是 f[u]

最后答案就是 f[S]。

复杂度：

  • 建树 + 一次非递归遍历 + 一次逆序DP
  • 时间 O(N)，空间 O(N)，能轻松过 1e5。
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vll=vector<ll>;
using vvll=vector<vector<ll>>;
using vc=vector<char>;
using vs=vector<string>;
using vb=vector<bool>;
using vpii=vector<pii>;
using vpll=vector<pll>;

const int INF=1e9;
const ll LINF=4e18;
const int MOD=1e9+7;
const int MOD2=998244353;

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ral(x) x.rbegin(),x.rend()
#define fi first
#define se second
#define fix(x) fixed<<setprecision(x)

ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}

ll qpow(ll a,ll b,ll mod=MOD){
	ll res=1;
	a%=mod;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

ll modinv(ll a,ll p=MOD){
	return qpow(a,p-2,p);
}

struct Node{
	int a,b;
	
	bool operator<(const Node &y)const{
		return b>y.b;
	}
};

void solve(){
    int n,m,s;cin>>n>>m>>s;
    vector<vector<pair<int,ll>>> g(n+1);
    vi d(n+1);
    for(int i=1;i<=m;++i){
        int u,v;ll w;cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        ++d[u];
        ++d[v];
    }
    vi p(n+1),ord;
    vll pw(n+1);
    ord.reserve(n);
    vi st;
    st.push_back(s);
    while(!st.empty()){
        int u=st.back();
        st.pop_back();
        ord.push_back(u);
        for(int i=0;i<(int)g[u].size();++i){
            int v=g[u][i].fi;
            if(v==p[u])continue;
            p[v]=u;
            pw[v]=g[u][i].se;
            st.push_back(v);
        }
    }
    vb has(n+1);
    vll f(n+1);
    for(int i=(int)ord.size()-1;i>=0;--i){
        int u=ord[i];
        if(d[u]==1&&u!=s){
            has[u]=1;
            f[u]=LINF;
            continue;
        }
        ll cur=0;
        bool ok=0;
        for(int j=0;j<(int)g[u].size();++j){
            int v=g[u][j].fi;
            ll w=g[u][j].se;
            if(p[v]!=u)continue;
            if(!has[v])continue;
            ok=1;
            cur+=min(w,f[v]);
        }
        has[u]=ok;
        f[u]=cur;
    }
    cout<<f[s]<<endl;
}

int main(){
	IOS;
	int _=1;//in>>_;
	while(_--){
		solve();
	}
	return 0;
}