牛客每日一题4.1 Rinne Loves Edges 树dp

https://blog.csdn.net/qq_43804974/article/details/105222630

首先理解题意后可以转化为
以S为根的树，用最少的权值去删除边，使得所有的叶子与S不相连。
如果可以得出上面的题意那这题就是个树dp简单题了。那么设
f[i] 为以i为根的子树，他的所有叶子都达不到i节点的最少权值花费。
显然方程就是f[i] = sum( min ( f [to], i与to相连的权) )
这个方程就是对于i的每一个儿子，你有两种选择，第一种是砍掉i与to相连的边，这样所有叶子都不会到达i，一种的利用f[to]算好的答案，取一个最小值
答案就是f[S]

int n, m, k,f[max_],du[max_];
vector<pair<int, int> >xian[max_];
void dfs(int now, int fa) {
    if (du[now] == 1 && now != k) {
        f[now] = INF; return;
    }
    for (auto pa : xian[now]) {
        int to = pa.first, val = pa.second;
        if (to == fa)continue;
        dfs(to, now);
        f[now] += min(f[to], val);
    }
}
signed main() {
    n = read(), m = read(), k = read();
    for (int i = 1; i < n; i++) {
        int a = read(), b = read(), c = read();
        xian[a].push_back(make_pair(b, c));
        xian[b].push_back(make_pair(a, c));
        du[b]++; du[a]++;
    }
    dfs(k, 0);
    write(f[k]);
    return 0;
}