NC22598 Rinne Loves Edges

题意：给出n个结点m条边的无向联通图 备注里说边的数量m恒等于n-1 那么就是一颗树 选出一个点s 使得所有度为1的结点都到不了s 度为1的点显然就是叶子结点

思路：既然是树形dp 那么就先思考下他们的子问题是什么 目标是使得所有叶子结点都到不了s 显然子问题要从子树开始入手 处理的方法也就两种 1是直接删除s和子树的联系 2是删除子树和叶子结点的联系 用dp[u]来代表叶子结点不能到根的最小代价 则转移方程为
"图片标题")

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;

struct Edge
{
    int to;
    int w;
    int next;
} edge[N << 1];

int head[N],cnt = 0;

int dp[N];
int de[N];

int n,m,s;

void addEdge(int u,int v,int w)
{
    edge[++ cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void dfs(int u,int v)
{
    if(de[u] == 1 && u != s)
    {
        dp[u] = INF;
        return ;
    }

    for(int i = head[u]; i != -1 ; i = edge[i].next)
    {
        int to = edge[i].to;

        if(to != v)
        {
            dfs(to,u);

            dp[u] += min(edge[i].w,dp[to]);
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);

    memset(head,-1,sizeof(head));

    for(int i = 0; i < m ; i ++)
    {
        int u, v, w;

        scanf("%d%d%d",&u,&v,&w);

        addEdge(u,v,w);
        addEdge(v,u,w);

        de[u] ++, de[v] ++ ;
    }

    dfs(s,0);

    printf("%d\n",dp[s]);

    return 0;
}