每日一题 4.1 Rinne Loves Edges

这题乍一看是一个图论 我不会啊啊啊 但看到m=n-1 发现这是一颗树 要度为一 百度一下发现树上度为一的节点那就只有叶节点了 于是这变成了一个树上dp（因为是求最优解）
如何不能到达 那就是切直接连的边或者子节点的边 求最小就判断一下谁更小就切谁
于是这个题就出来了 代码有详细注释QAQ 使用链式前向星存图

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define inf 1e18
ll const maxn=2e5+10;
struct M{///链式前向星存图
    ll to,next,val;///终点，同起点的上一条边的编号，边权
}edge[maxn];///边集
ll n,m,s,u,v,w,cnt,head[maxn],f[maxn],du[maxn];
void add(ll u,ll v,ll w)
{
  edge[++cnt].next = head[u];///以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
  edge[cnt].to=v;///终点
  edge[cnt].val=w;///权值
  head[u]=cnt;///更新以u为起点上一条边的编号
}
void dfs(ll u,ll fa) {
  if (du[u]==1&&u!=s)///为叶子节点
  {
    f[u]=inf;///初始化为最大
    return;
  }
  for (ll i=head[u];i!=0;i=edge[i].next)///遍历以i为起点的边
  {
    if (edge[i].to!=fa) ///fa为0 判断是否到底了
    {
      dfs(edge[i].to,u);
      f[u]+=min(f[edge[i].to], edge[i].val);///看是直接连的边小 还是子节点的边小
                                            ///一步步回推形成最小解
    }
  }
}
int main() {
  scanf("%d%d%d",&n,&m,&s);
  for(ll i=1;i<=n-1;++i)
  {
    scanf("%d%d%d",&u,&v,&w);///u,v节点 w权值
    add(u,v,w);
    add(v,u,w);
    du[u]++,du[v]++;///度为一 那就只有一条边相连 就是叶节点
  }
  dfs(s,0);///以s为根节点
  cout<<f[s]<<endl;
  return 0;
}