solution

因为m=n,所以题目要求也就是要求断掉一些边,使得根与叶子节点不连通,用f[i]表示以i已经无法到达它子树中的所有叶子节点的最小花费。

转移的时候分两种情况,如果断开当前点与父亲相连的边,那么其子树中的边可以都不断开,花费为0.
如果不断开当前点与父亲相连的边,那么答案就是其儿子的f值之和。

树形dp即可。

code

/*
* @Author: wxyww
* @Date: 2020-04-02 20:47:38
* @Last Modified time: 2020-04-02 22:53:06
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt,w;
}e[N << 1];
int head[N],ejs;
void add(int u,int v,int w) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
ll f[N];

void dfs(int u,int fa) {
    ll sum = 0;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        f[v] = e[i].w;
        // printf("%d\n",e[i].w);
        dfs(v,u);
        sum += f[v];
    }
    if(sum)
    f[u] = min(f[u],sum);
}

int main() {
    memset(f,0x3f,sizeof(f));
    int n = read(),m = read(),S = read();
    for(int i = 1;i < n;++i) {
        int u = read(),v = read(),w = read();
        add(u,v,w);add(v,u,w);
    }
    dfs(S,0);
    cout<<f[S];
    return 0;
}