每日一题 4月1日 Rinne Loves Edges 树形DP

#include<bits/stdc++.h>
#define LL long long
using namespace std;

struct node{
    LL to, w;
};
vector<vector<node> > v(100005);
LL f[100005];

void dfs(int u, int fa){
    if(v[u].size()==1&&v[u][0].to==fa){
        f[u]=1ll<<60;
        return ;
    }
    for(auto x: v[u]){
        LL to=x.to, w=x.w;
        if(to!=fa){
            dfs(to, u);
            if(w<f[to]){
                f[to]=w;
            }
            f[u]+=f[to];
        }
    }
}

int main(){

    int n, m, s, x, y, z;
    scanf("%d%d%d", &n, &m, &s);
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &x, &y, &z);
        v[x].push_back(node{y, z});
        v[y].push_back(node{x, z});
    }
    dfs(s, 0);
    cout<<f[s]<<endl;

    return 0;
}