#include <bits/stdc++.h> #define Pc_champs ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL); #define int long long #define ll long long using namespace std; int const N = 5e3 + 1, LOG = 18, N2 = 1e5 + 1, SQ = 710, M = 1e9 + 7; int const MX = (int) 1e12; vector<vector<pair<int, int>>> adj; vector<int> dp[2][N]; vector<int> val; vector<int> mrg(vector<int> a, vector<int> b) { vector<int> combine(a.size() + b.size() - 1, MX); for (int i = 0; i < a.size(); ++i) { for (int j = 0; j < b.size(); ++j) { combine[i + j] = min(combine[i + j], a[i] + b[j]); } } return combine; } void dfs(int u, int v = 0) { dp[0][u] = {0}; dp[1][u] = {0}; for (auto i: adj[u]) { if (i.first == v)continue; val[i.first] = i.second; dfs(i.first, u); vector<int> cur = mrg(dp[1][u], dp[0][i.first]); dp[1][u] = mrg(dp[0][u], dp[1][i.first]); for (int j = 0; j < cur.size(); ++j) dp[1][u][j] = min(dp[1][u][j], cur[j]); dp[0][u] = mrg(dp[0][u], dp[0][i.first]); } dp[0][u].emplace_back(); dp[1][u].emplace_back(); for (int i = dp[0][u].size() - 1; i; --i) { dp[0][u][i] = dp[0][u][i - 1] + 2 * val[u]; dp[1][u][i] = dp[1][u][i - 1] + val[u]; } } int n, k, x, idx; void dowork() { cin >> n >> k >> x; adj = vector<vector<pair<int, int>>>(n + 1); val = vector<int>(n + 1); for (int i = 0, u, v, c; i < n - 1; ++i) { cin >> u >> v >> c; adj[u].emplace_back(v, c); adj[v].emplace_back(u, c); } dfs(x); cout << dp[1][x][k]; } signed main() { Pc_champs int t = 1; //cin >> t; while (t--) { ++idx; dowork(); cout << '\n'; } }