【每日一题】Rinne Loves Edges

戳我传送


题意：
这个题意是关键，首先n个点n-1条无向边边，接触过树的同学应该都知道这是一颗树，而度就是与这个点相连的边的数量，度为1就是叶子结点了，现在问题就变成了：在以S为根的树上删掉权值之和尽量小的一些边使得根和每一个叶子节点都不连通。
思路：
这是一个典型的树型dp，而树型dp本质上可以说是个搜索——遍历这棵树，在返回的时候维护相关的值。不管是写dp还是写搜索其实都是要分析原问题和子问题分别是什么的，我们要分析的大问题就是使s和所有的叶子都不联通的最小代价是多少，小问题就是s的儿子和子树上的叶子都不联通的最小代价是多少。因为s可以选择断掉和儿子的边，或者让儿子与子树的叶子结点不连通，所以转移方程为： ,g[x][v]指删除x和儿子v边的代价。（注意叶子结点的f [ ]应该是无穷大）
Code：

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
ll f[maxn],val[maxn<<1];
int head[maxn],Next[maxn<<1],to[maxn<<1],tot;
void add(int x,int y,ll c) {
    to[++tot]=y;
    val[tot]=c;
    Next[tot]=head[x];
    head[x]=tot;
}
void dfs(int x,int fa) {
    bool flag=true;
    for(int i=head[x];i;i=Next[i]) {
        int y=to[i];
        if(y==fa)    continue;
        dfs(y,x);
        flag=false;
        f[x]+=min(f[y],val[i]);
    }
    if(flag) f[x]=0x3f3f3f3f3f3f3f3f; 
}
int n,m,s;
int main() {
    read(n),read(m),read(s);
    for(int i=1;i<=m;++i) {
        int x,y; ll z;
        read(x),read(y),read(z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs(s,0);
    printf("%lld\n",f[s]);
    return 0;
}