模拟赛写的。

定义 $f_i$ 为第 $i$ 个节点和它父亲节点的那条边要使用的次数。

那么 $f_i=\min\limits_{v\in son }f_v$。同时记得减 $f_v$ 的。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 500001

int n, u, v, w, s, maxn, ans;
int dis[MAXN], f[MAXN];
vector<pair<int, int>> e[MAXN];

void dfs(int x, int f){
    for (auto i: e[x]){
        int v(i.first);
        if (v ^ f){
            dis[v] = dis[x] + i.second;
            dfs(v, x);
        }
    }
}

void dfs2(int x, int fa){
    if (e[x].size() == 1){
        f[x] = maxn-dis[x];
        return;
    }
    int res(LLONG_MAX);
    for (auto i: e[x]){
        int v(i.first);
        if (v ^ fa){
            dfs2(v, x);
            res = min(res, f[v]);
        }
    }
    if (x == s) return;
    f[x] = res;
    for (auto i: e[x]){
        int v(i.first);
        if (v ^ fa) f[v] -= res;
    }
}

signed main(){
    // freopen("ex_data1.in", "r", stdin);
    // freopen("ex_data1.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> s;
    for (int i(1); i<n; ++i){
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dfs(s, 0);
    for (int i(1); i<=n; ++i) maxn = max(maxn, dis[i]);
    dfs2(s, 0);

    for (int i(1); i<=n; ++i){
        if (i ^ s) ans += f[i];
    }
    cout << ans;

    return 0;
}