【每日一题】4月1日 Rinne Loves Edges

个人博客：在最前面发一下自己这个寒假刚弄的个人博客，很弱鸡，膜各位大佬。

在题干中划重点：个节点条边的无向连通图且，所以这是一颗树呐。

再划重点：原图中所有初之外度为1的点，弱弱的问萌新们，这是什么点？？？叶子节点呐。

理清题意：每条边有一个边权，希望删除一些边使得叶子节点都不能到达点。

明显的WA：萌新可能很容易想到把点到叶子节点路径上权值最小的边删掉，总代价就最小，很显然，这是错误的。提供反例：4 3 1，1 2 3，2 3 2,2 4 2。这棵树1为根节点，3和4分别为叶子节点，路径上权值最小的边都是2，总和为4，但显然最小代价为3。

正解：如上图所示，假设点有颗子树，对于每颗子树可以选择删除边，也可以选择删除子树中的边，两者取最小值即可。那怎么知道子树删哪些边呢？？？显然这是一个递归的套娃问题。而对于叶子节点我们取无穷大即可。

代码隐患：题目只说有权值并保证答案在c++ long long范围内，那么是不是权值可以为负呢？下面的代码并没有考虑这种情况，直接莽过了。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e5 + 117;

int n, m, s;
struct Edge {
    int v;
    LL w;
    int ne;
} edge[MAXN];
bool vis[MAXN];
int head[MAXN], tot;
void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(vis, false, sizeof(vis));
}
void addedge(int u, int v, LL w) {
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
LL dfs(int id) {
    vis[id] = true;
    LL ret = (LL)INF * INF, sum = 0, num;
    for(int i = head[id]; i != -1; i = edge[i].ne) {
        if(vis[edge[i].v]) continue;
        num = dfs(edge[i].v);
        sum += min(num, edge[i].w);
    }
    if(sum) return sum;
    return ret;
}
int main() {
    init();
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 0; i < m; i++) {
        int u, v;
        LL w;
        scanf("%d%d%lld", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    printf("%lld\n", dfs(s));
    return 0;
}