【每日一题】Rinne Loves Edges

题意：原本一颗无根树，以s为根结点拉起，求这颗树中任意叶子结点都不可到达s的最小代价

dp[u]表示以u为根的子树中的所有叶子结点都到达不了u的最小代价

①u是叶子结点时dp[u] = inf;
②其余 dp[u]:for(int v : son[u]){ dp[u] += min(dp[v],edge(u,v));}
对于叶子结点无法做到自己不可达自己，而对于其他结点u要么令叶子结点不可达u的子节点，要么自己断去子节点的边(另外忘了无向图边数乘2，一直RE。。。。。。)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const ll inf = 1e18;
int n,m,s,idx;
int head[N],in[N];
ll dp[N];
struct Edge{
    int to,nex;
    ll w;
}e[N];
void addedge(int u,int v,ll w){
    e[idx].to = v;
    e[idx].nex = head[u];
    e[idx].w = w;
    head[u] = idx++;
}
void dfs(int u,int fa){
    if(in[u] == 1&&u!=s){
        dp[u] = inf;
        return;
    } 
    for(int i = head[u];~i;i = e[i].nex){
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v,u);
        dp[u]+=min(dp[v],e[i].w);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    memset(head,-1,sizeof(head));
    for(int i = 0;i < m;i++){
        int u,v;ll w;
        scanf("%d%d%lld",&u,&v,&w);
        addedge(u,v,w);addedge(v,u,w);
        in[u]++,in[v]++;
    }
    dfs(s,-1);
    printf("%lld\n",dp[s]);
    return 0;
}