| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 975313 | dosts | Museum (CEOI17_museum) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define vi vector<int>
const int N = 5e3+1,inf = 1e18,MOD = 998244353;
int dp[N][2][N];
vector<pii> edges[N];
vi sz(N);
int szs(int node,int p) {
sz[node] = 1;
for (auto it : edges[node]) if (it.ff != p) sz[node]+=szs(it.ff,node);
return sz[node];
}
int K;
void compute(int node,int p) {
int curmx = 1;
for (auto it : edges[node]) {
if (it.ff == p) continue;
int u = it.ff,w = it.ss;
compute(u,node);
curmx+=sz[u];
for (int i=curmx;i>=2;i--) {
for (int j=max(0ll,-curmx+sz[u]+i);j<=min(i,sz[u]);j++) {
dp[node][0][i] = min(dp[node][0][i],dp[node][0][i-j] + dp[u][1][j]+ 2*w);
dp[node][1][i] = min(dp[node][1][i],dp[node][1][i-j] + dp[u][1][j]+ 2*w);
dp[node][0][i] = min(dp[node][0][i],dp[node][1][i-j] + dp[u][0][j] + w);
}
}
}
}
void solve() {
int n,x;
cin >> n >> K >> x;
for (int i=1;i<=n-1;i++) {
int u,v,w;
cin >> u >> v >> w;
edges[u].push_back({v,w});
edges[v].push_back({u,w});
}
for (int i=1;i<=n;i++) for(int j=0;j<2;j++) for (int k=2;k<=n;k++) dp[i][j][k] = inf;
szs(x,x);
compute(x,x);
cout << dp[x][0][K] << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}