牛客 Rinne Loves Edges（dp）

答案肯定是在子树中断开叶节点和断开当前点和子树点的边中的最小值

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
const int mod=1e9+7;
typedef long long ll;
int h[N],ne[N],e[N],idx;
int w[N];
int f[N];
int in[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int n,m,s;
void dfs(int u,int fa){
    int i;
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)
            continue;
        dfs(j,u);
        f[u]+=min(f[j],w[i]);
    }
    if(in[u]==1&&u!=s){
        f[u]=0x3f3f3f3f;
    }
}
int main(){
    cin>>n>>m>>s;
    int i;
    memset(h,-1,sizeof h);
    for(i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
        in[a]++;
        in[b]++;
    }
    dfs(s,-1);
    cout<<f[s]<<endl;
}