题意

给定一棵树和根节点，每条边有边权。删去一些边，使得根节点和叶子节点不连通，求删的边的边权和最小值。

分析

树形dp。
令 表示 不与子树中的叶子节点相连的最小值。
考虑 的每一个儿子 和边权
显然断 中叶子节点的最优值为
然后 即可。

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 100005
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
LL read(){
    LL x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
struct node{
    int a, b, n;
    LL c;
}d[N * 2];
int cnt, h[N], a[N], fa[N];
LL f[N];
void cr(int a, int b, LL c){
    d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a){
    int i, b;
    LL c, s = 0, zhi = 0;
    f[a] = (z << 40);
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b;
        c = d[i].c;
        if(b == fa[a]) continue;
        zhi = 1;
        fa[b] = a;
        dfs(b);
        s += min(c, f[b]);
    }
    if(zhi == 1) f[a] = s;
}
int main(){
    int i, j, n, m, s, a, b, c;
    n = read(); m = read(); s = read();
    for(i = 1; i <= m; i++){
        a = read(); b = read(); c = read();
        cr(a, b, c);
        cr(b, a, c);
    }
    dfs(s);
    printf("%lld", f[s]);
    return 0;
}