【每日一题】Rinne Loves Edges（dfs+dp求解)

首先我们可以注意到最后一行m=n-1,那么这个无向连通图就是一棵树了。那么再仔细的分析下，题目要求除了s之外度为1的点都不能到达s，那么除了s之外的度为1 的点就是叶子节点了，那么问题转化为了 如何删掉边权最短的一些边，从而使得s到不了任何一个（注意是任何一个）叶子节点。 思索了一下，这个题应该可以dfs+dp求解，我们可以令dfs(u)返回 u这个点到不了任何一个叶子节点的最小代价，那么对于任何一个点u 和它的非父亲节点v有两种选择。

• 选择删除u和v连着的边 即Wuv
• 选择删除使得v到不了任何一个子节点的代价，即dp[v] 那么我们就只要对这两种情况取min就可以。最后记得开long long保险起见。 然后就快乐dfs ~~~ 最后就ac啦~~

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
typedef pair<ll,ll> pll;
vector<pll> edge[N];
ll n,m,s,dp[N],vis[N];
void dfs(int x)
{
    vis[x]=1;
    int isye=1;
    for(auto xx:edge[x])
    {
         
        ll v=xx.first,w=xx.second;
        if(!vis[v]){
            isye=0;
            dfs(v);
            dp[x]+=min(dp[v],w);
        }
    }
    if(isye) dp[x]=1e18;
    return;
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&s);
    while(m--)
    {
        ll u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        edge[u].push_back(make_pair(v,w));
        edge[v].push_back(make_pair(u,w));
    }
    dfs(s);
    printf("%lld",dp[s]);
}

</ll,ll>