#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include <C:\debug.hpp>
#endif // ONLINE_JUDGE
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "migration"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 5000 + 7
using namespace std;
const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r)(rng);
}
int n, k, rt;
vector<ll> dp[maxn][2];
vector<pair<int, int>> edges[maxn];
vector<ll> Min(vector<ll> &A, vector<ll> &B) {
while(A.size() < B.size()) A.push_back(1e18);
fi(i, 0, B.size() - 1) A[i] = min(A[i], B[i]);
return A;
}
vector<ll> cb(const vector<ll> &A, const vector<ll> &B, ll w) {
vector<ll> ans(A.size() + B.size() - 1, 1e18);
fi(i, 0, A.size() - 1) fi(j, 0, B.size() - 1) {
ans[i + j] = min(ans[i + j], A[i] + B[j] + (j > 0) * w);
}
return ans;
}
void dfs(int u, int par) {
fi(i, 0, 1) dp[u][i] = {0, 0};
for(auto [v, w] : edges[u]) if(v != par) {
dfs(v, u);
vector<ll> tmp1 = cb(dp[u][0], dp[v][1], w);
vector<ll> tmp2 = cb(dp[u][1], dp[v][0], 2 * w);
dp[u][1] = Min(tmp1, tmp2);
dp[u][0] = cb(dp[u][0], dp[v][0], 2 * w);
}
}
void solve()
{
cin >> n >> k >> rt;
fi(i, 1, n - 1) {
int x, y, w; cin >> x >> y >> w;
edges[x].push_back({y, w}), edges[y].push_back({x, w});
}
dfs(rt, 0);
// fi(i, 1, n) cout << dp[1][1][i] << "\n";
cout << dp[rt][1][k];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(Neco".inp", "r")) {
freopen(Neco".inp", "r", stdin);
freopen(Neco".out", "w", stdout);
}
int nTest = 1;
// cin >> nTest;
while(nTest--)
{
solve();
}
return 0;
}
Compilation message
museum.cpp:3:10: fatal error: C:\debug.hpp: No such file or directory
3 | #include <C:\debug.hpp>
| ^~~~~~~~~~~~~~
compilation terminated.
