#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define f first
#define s second
/**
* The challenge of the problem is to know which edges we want to "backtrack" on (meaning we pass an edge twice).
* It is key that we realize the given graph is a tree, which means we can use tree DP.
*
* Let dp[i][j][0/1] = the min cost to visit j nodes in subtree of i, such that 0 = we don't return back to i, 1 = we return back to i
*/
struct edge{
int to, c;
};
const int MAXN = 10001;
int n, k, x, ss[MAXN], dp[MAXN][MAXN][2], dp2[MAXN][MAXN][2];
vector<edge> arr[MAXN];
void subtreeSize(int at, int par){
ss[at] = 1;
for (edge i : arr[at]){
if (i.to != par){
subtreeSize(i.to, at);
ss[at] += ss[i.to];
}
}
}
void dfs(int at, int par){
// try to "tack on" the answer of the children of at
int currSize = 1;
for (edge i : arr[at]){
if (i.to != par){
dfs(i.to, at);
// combine the new subtree with the existing subtree of at
for (int atSize=1; atSize<=currSize; atSize++){
for (int newSize=1; newSize<=ss[i.to]; newSize++){
dp2[at][atSize + newSize][0] = min({dp2[at][atSize + newSize][0], dp[at][atSize][1] + dp[i.to][newSize][0] + i.c, dp[at][atSize][0] + dp[i.to][newSize][1] + 2*i.c});
dp2[at][atSize + newSize][1] = min(dp2[at][atSize + newSize][1], dp[at][atSize][1] + dp[i.to][newSize][1] + 2*i.c);
}
}
// copy over data
for (int atSize=1; atSize<=currSize; atSize++){
for (int newSize=1; newSize<=ss[i.to]; newSize++){
dp[at][atSize + newSize][0] = min(dp[at][atSize + newSize][0], dp2[at][atSize + newSize][0]);
dp[at][atSize + newSize][1] = min(dp[at][atSize + newSize][1], dp2[at][atSize + newSize][1]);
}
}
for (int atSize=1; atSize<=currSize; atSize++){
for (int newSize=1; newSize<=ss[i.to]; newSize++){
dp2[at][atSize + newSize][0] = dp2[at][atSize + newSize][1] = INT_MAX;
}
}
currSize += ss[i.to];
}
}
}
int main(){
cin.tie(0); ios_base::sync_with_stdio(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
cin >> n >> k >> x;
x--;
for (int i=0; i<n-1; i++){
int a, b, c;
cin >> a >> b >> c;
a--; b--;
arr[a].push_back({b, c});
arr[b].push_back({a, c});
}
for (int i=0; i<MAXN; i++){
for (int j=0; j<MAXN; j++){
if (j > 1){
dp[i][j][0] = dp[i][j][1] = INT_MAX;
}
dp2[i][j][0] = dp2[i][j][1] = INT_MAX;
}
}
subtreeSize(x, -1);
dfs(x, -1);
cout << dp[x][k][0] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
571 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
455 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
455 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
571 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
