每日一题4月1日（树形DP）

思路：要达成题目要求我们有2种方法1.删除s和子树之间的节点2.删除子树与叶子的节点。那么我们将f[i]表示为以结点i为根节点的最小代价可得f[i]+=min(f[i],wi...j)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <sstream>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cstdlib>
#define MAXX 100005
#define SIS std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
//#include<bits/stdc++.h>
using namespace std;
const int MAX =2e5+20;
const double PI = 3.14159265359;

//const int mod = 1e9 + 7;
struct node{
  ll to,nex,val;
}edge[MAX];
ll n,m,s, cnt=0,head[MAX],f[MAX],d[MAX];

void add(ll u,ll v,ll w)
{
    cnt++;
    edge[cnt].to=head[u];
    edge[cnt].val=w;
    edge[cnt].nex=v;
    head[u]=cnt;
}
void dfs(ll u,ll fa)
{
    if(d[u]==1&&u!=s)
        return ;
    f[u]=0;
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        if(edge[i].nex!=fa){
            dfs(edge[i].nex,u);
            f[u]+=min(f[edge[i].nex],edge[i].val);
        }
    }
    return ;
}
int main()
{
    SIS;
    cin>>n>>m>>s;
    ll u,v,w;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
        d[u]++,d[v]++;

    }
    memset(f,INF,sizeof(f));
    dfs(s,0);
    cout<<f[s]<<endl;
    return 0;

}