#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10;
struct yal{
int u,v,w;
int getad(int fu){
return (u^v^fu);
}
}alle[maxn];
vector<int>adj[maxn];
int sz[maxn],n,x,k,inf=1e9;
vector<int>dp[maxn],pd[maxn];
void vorod(){
cin>>n>>k>>x;
for(int i=0;i<n-1;i++){
cin>>alle[i].u>>alle[i].v>>alle[i].w;
adj[alle[i].u].push_back(i);
adj[alle[i].v].push_back(i);
}
}
void add(int u,int w){
for(int i=1;i<(int)dp[u].size();i++){
dp[u][i]+=w;
pd[u][i]+=2*w;
}
}
vector<int>fake,fakea;
void merge(int u,int v){
int szu=dp[u].size(),szv=dp[v].size();
// vector<int>fake(szu+szv-1,inf),fakea(szu+szv-1,inf);
fake.clear();
fakea.clear();
fake.resize(szu+szv-1,inf);
fakea.resize(szu+szv-1,inf);
for(int i=0;i<szu;i++){
for(int j=0;j<szv;j++){
fake[i+j]=min(fake[i+j],dp[u][i]+pd[v][j]);
fake[i+j]=min(fake[i+j],pd[u][i]+dp[v][j]);
fakea[i+j]=min(fakea[i+j],pd[u][i]+pd[v][j]);
}
}
dp[u].swap(fake);
pd[u].swap(fakea);
}
void dfs(int u,int par=-1){
dp[u].resize(2);
pd[u].resize(2);
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v==par){
continue;
}
dfs(v,u);
add(v,alle[x].w);
merge(u,v);
}
// cout<<"hey: "<<u<<" "<<par<<endl;
// for(auto x:dp[u]){
// cout<<x<<" ";
// }
// cout<<"\n";
// for(auto x:pd[u]){
// cout<<x<<" ";
// }
// cout<<"\n";
}
void solve(){
dfs(x);
}
void khor(){
cout<<dp[x][k]<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("inp.txt","r",stdin);
vorod();
solve();
khor();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
3924 KB |
Output is correct |
2 |
Correct |
94 ms |
4180 KB |
Output is correct |
3 |
Correct |
220 ms |
154180 KB |
Output is correct |
4 |
Correct |
141 ms |
48980 KB |
Output is correct |
5 |
Correct |
103 ms |
12892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
3924 KB |
Output is correct |
2 |
Correct |
94 ms |
4180 KB |
Output is correct |
3 |
Correct |
220 ms |
154180 KB |
Output is correct |
4 |
Correct |
141 ms |
48980 KB |
Output is correct |
5 |
Correct |
103 ms |
12892 KB |
Output is correct |
6 |
Correct |
96 ms |
4616 KB |
Output is correct |
7 |
Correct |
170 ms |
92752 KB |
Output is correct |
8 |
Correct |
306 ms |
2644 KB |
Output is correct |
9 |
Correct |
229 ms |
2968 KB |
Output is correct |
10 |
Correct |
113 ms |
3848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1116 KB |
Output is correct |
6 |
Correct |
95 ms |
3924 KB |
Output is correct |
7 |
Correct |
94 ms |
4180 KB |
Output is correct |
8 |
Correct |
220 ms |
154180 KB |
Output is correct |
9 |
Correct |
141 ms |
48980 KB |
Output is correct |
10 |
Correct |
103 ms |
12892 KB |
Output is correct |
11 |
Correct |
96 ms |
4616 KB |
Output is correct |
12 |
Correct |
170 ms |
92752 KB |
Output is correct |
13 |
Correct |
306 ms |
2644 KB |
Output is correct |
14 |
Correct |
229 ms |
2968 KB |
Output is correct |
15 |
Correct |
113 ms |
3848 KB |
Output is correct |
16 |
Correct |
95 ms |
4436 KB |
Output is correct |
17 |
Correct |
94 ms |
4344 KB |
Output is correct |
18 |
Correct |
144 ms |
57908 KB |
Output is correct |
19 |
Correct |
245 ms |
2916 KB |
Output is correct |
20 |
Correct |
101 ms |
4464 KB |
Output is correct |
21 |
Correct |
164 ms |
85224 KB |
Output is correct |
22 |
Correct |
104 ms |
4192 KB |
Output is correct |
23 |
Correct |
246 ms |
2644 KB |
Output is correct |
24 |
Correct |
99 ms |
4480 KB |
Output is correct |
25 |
Correct |
227 ms |
147688 KB |
Output is correct |