【每日一题】树上DFS

树上DP

https://ac.nowcoder.com/acm/problem/22598

题目：在以S为根的树上删掉权值和尽量小的一些边使得S和每一个叶子节点都不连通。
关于树的题目真是丰富啊====
树是最能体现递归的，递归是从顶向下的，转化成从底向上就变成了DP，所以“树上”的题目真是前变万化~
子问题：以x为根的子树上的所有叶子和根断开的最小代价
dfs转移时候选择断开与儿子的边还是断开儿子字树的边即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 * 2 +10 ;
ll f[maxn/2];// f[x]表示x的子树上的所有叶子和根断开的最小代价
int p[maxn],h[maxn],ne[maxn],edge[maxn];
int num=0;

void addEdge(int from, int to,int w){ 
    p[++num] = to;//to->from
    ne[num] = h[from];
    h[from] = num;
    edge[num]=w;
    p[++num] = from;
    ne[num] = h[to];
    h[to]=num;
    edge[num]=w;
}
int inD[maxn/2];//入度
int n,m,s;
void dfs(int u,int fa)
{
    if(inD[u] == 1 && u != s){
        f[u] = 0x3f3f3f3f;
        return;
    }
    for(int i = h[u];i;i = ne[i])if(p[i]!=fa)
    {
        int child = p[i],w = edge[i];
        dfs(child,u);
        f[u] += min(1ll*w,f[child]);
    }
}
int main()
{
   // freopen("1.in","r",stdin);
    scanf("%d %d %d",&n,&m,&s);
    for(int i = 1 ;i <= m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        addEdge(u,v,w);
        ++inD[u],++inD[v];
    }
    dfs(s,0);
    cout<<f[s];
    return 0;
}