#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define ins insert
#define pb push_back
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<
const int mod = 1e9+7 ,
sze= 2e5 + 23 ,
inf = 1e13,
L = 31 ;
vector<pair<int,int>> graph[sze];
vector<int> alst;
int dp[sze][2];
void dfs(int node,int par,int mid){
for(auto [a,b]:graph[node]){
if(a!=par){
dfs(a,node,mid);
dp[node][0] = min(dp[node][0],dp[a][0] + b);
if(dp[a][1] + b <= mid){
dp[node][1]=max(dp[node][1],dp[a][1] + b);
}
else{
// cout<<mid<<" => "<<a<<endl;
alst.pb(a);
dp[node][0]=min(dp[node][0],b);
}
}
}
if(dp[node][0] + dp[node][1] <= mid){
dp[node][1]=-inf;
}
// cout<<mid<<"=> " _ node _ dp[node][0] _ dp[node][1]<<endl;
}
int check(int mid){
alst.clear();
for(int i=0;i<=sze;i++){
dp[i][0]=inf;
dp[i][1]=0;
}
dfs(1,0,mid);
if(dp[1][0] + dp[1][1] > mid){
alst.pb(1);
}
return alst.size();
}
void opt1z(){
int n,k;
cin>>n>>k;
for(int i =1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
graph[u].pb({v,w});
graph[v].pb({u,w});
}
int l =1;
int r = (int)2e9 * (int)2e5;
int ans=1;
while(l<=r){
int mid = (l+r)/2;
if(check(mid)<=k){
ans = mid;
r = mid -1;
}
else{
l = mid+1;
}
}
check(ans);
set<int> a;
for(auto v:alst){
a.ins(v);
}
for(int i=1;i<=n;i++){
if(a.size()<k && a.find(i)==a.end()){
a.ins(i);
// cout<< "new " _ i<<endl;
}
}
cout<<ans<<"\n";
for(auto v:a) cout<<v<<" ";cout<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
// cin>>tt;
while(tt--){
opt1z();
}
return 0;
}
Compilation message
Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:18:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
18 | for(auto [a,b]:graph[node]){
| ^
Main.cpp: In function 'void opt1z()':
Main.cpp:83:20: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
83 | if(a.size()<k && a.find(i)==a.end()){
| ~~~~~~~~^~
Main.cpp:89:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
89 | for(auto v:a) cout<<v<<" ";cout<<endl;
| ^~~
Main.cpp:89:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
89 | for(auto v:a) cout<<v<<" ";cout<<endl;
| ^~~~
Main.cpp: In function 'long long int check(long long int)':
Main.cpp:41:17: warning: iteration 200023 invokes undefined behavior [-Waggressive-loop-optimizations]
41 | dp[i][0]=inf;
| ~~~~~~~~^~~~
Main.cpp:40:18: note: within this loop
40 | for(int i=0;i<=sze;i++){
| ~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
16476 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
104 ms |
78928 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
151 ms |
83092 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
16476 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
