【每日一题】Rinne Loves Edges (树形DP)

Solution
简单来说题目就是求在有根树中，每个叶子节点到根节点的路径上的边权最小值之和，很典型的树形DP。
s为根，考虑 dp[s] 为答案，即每个叶子节点到s的路径上的边权最小值之和，
那么 dp[s]= Σ min（dp[s.son] , s->s.son的边权) 。
最后注意一下叶子节点是没有出边的，所以 dp 值设为 inf 。

Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("YES") ;}void put2(){ puts("NO") ;}void put3(){ puts("-1"); }

const int manx=1e5+5;

vector<pair<ll,ll> >g[manx];
ll dp[manx],d[manx];

void dfs(ll u,ll pre){
    if(pre!=0&&d[u]==1) return ;
    dp[u]=0;
    for(auto x: g[u]){
        ll v=x.fi,w=x.se,res=inf;
        if(v==pre) continue;
        dfs(v,u);
        dp[u]+=min(dp[v],w);
    }
}

int main(){
    ll n=read(),m=read(),s=read();
    for(int i=1;i<=m;i++){
        ll u=read(),v=read(),w=read();
        g[u].pb(mp(v,w));
        g[v].pb(mp(u,w));
        ++d[u],++d[v];
    }
    memset(dp,inf,sizeof(dp));
    dfs(s,0);
    printf("%lld",dp[s]);
    return 0;
}