下载pdf，获得更好阅读体验。
提取码：ke7w。

upd：这好像是 08 年哪个省省选题原题

题意转化

毒瘤出题人把 放在最后，害得眼睛不好的选手一开始没看到想了好长时间...

为一棵树

那这样就是一棵根为 的树上删除若干条边，使得所有叶子结点都与根不连通。

树形 DP

画一棵树，假设 有 个子树

根据 DP 子问题的思想，我们已经知道了下面 个子树，使得其叶子结点不能到 的最小代价。

此时，对于子树 ，有两种方案：一种是采取子树决策的方案，一种是删掉 的边，显然取最小更优。

对于叶子结点，子树决策为 即可。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100000 + 7;
const int maxm = 200000 + 7;
const long long INF = 0x3f3f3f3f3f3f3f3fll;

int n, m, S;
int Head[maxn], Next[maxm], to[maxm], tot, w[maxm];

long long dp[maxn];

void addedge(int x, int y, int z) {
    to[++tot] = y, Next[tot] = Head[x], Head[x] = tot, w[tot] = z;
}
void add(int x, int y, int z) {
    addedge(x, y, z); addedge(y, x, z);
}

void dfs(int x, int f) {
    bool son = false;
    for(int i = Head[x]; i; i = Next[i]) {
        int y = to[i];
        if(y == f) continue;
        son = true;
        dfs(y, x);
        dp[x] += min((long long)w[i], dp[y]);
    }
    if(!son) dp[x] = INF;
}

int main(void) {
    scanf("%d%d%d", &n, &m, &S);
    for(int i = 1, x, y, z; i < n; i++) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dfs(S, 0);
    printf("%lld\n", dp[S]);
}

另一种做法

这种做法可以解决一般图的问题

将 作为超级源点，所有度为 的点连接超级汇点，跑一遍最小割。

代码就是贴个模板的事情，就不放了。