牛客每日一题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;
} 