题解 | Rinne Loves Edges

最开始读题，很容易想到用dfs，但是又得保证全局最优解，这时候只用dfs就不行了，需要用dfs加dp，所以这是一道树形dp

我们只需要推出状态转移方程

除了s以外度为1的点，不难想到就是叶节点，我们遍历到叶节点时将叶节点的dp值初始化为INF，因为我们最开始肯定想把连着叶节点的那条边删去，后面再做优化，看有没有总和更小的方法，假设一个情况是，一条主干分了两个叶节点，我们肯定先算出了两个叶节点边切断的边权和，如果这条主干有边权更小的，直接取这个最小值即可

因此状态转移方程为dp[u] += min(dp[v] , w)

接下来只需要写出代码即可:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x << ": " << x << '\n';
const int INF = 0x3f3f3f3f3f3f3f3f;
//倒序不要忘记是--不是++
void solve(){
    int n,m,s;cin>>n>>m>>s;
    vector<vector<pair<int,int>>> e(n+1);
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    vector<int> dp(n+1);
    auto dfs=[&](auto dfs,int u,int fa)->void{
        if(u!=s&&e[u].size()==1) dp[u]=INF;
        // debug(u);
        for(auto i:e[u]){
            auto [v,w]=i;
            if(v==fa) continue;
            dfs(dfs,v,u);
            dp[u]+=min(dp[v],w);
        }
    };
    dfs(dfs,s,0);
    cout<<dp[s];
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}