#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+2;
const ll offset=1e9;
const ll block=317;
const ll inf=1e18;
const ll mod=1e9+7;
int n,k,g,up[maxn],selllll;
bool ed[maxn];
vector<pii> adj[maxn];
vector<int> res;
void cc(int u,int pass)
{
// cerr<<"asdasd "<< u<<'\n';
res.pb(u);
up[u]=pass;
ed[u]=1;
selllll++;
}
void dfs(int u,int pre,int last)
{
//cerr<<u<<'\n';
for(auto x: adj[u])
{
int v=x.fi,w=x.se;
if (v==pre) continue;
dfs(v,u,w);
}
if (last>g)
{
cc(u,last);
return;
}
int mx1=0,mx2=0;
for(auto x: adj[u])
{
int v=x.fi,w=x.se;
if (v==pre) continue;
if (last+up[v]>g && !ed[v])
{
cc(u,last);
return;
}
if (!ed[v])
{
if (up[v]>= mx1)
{
mx2=mx1;
mx1=up[v];
}
else if (up[v]>=mx2)
{
mx2=up[v];
}
}
}
// if (u==3)
// {
// cerr<< mx1<<' '<< mx2<<'\n';
// }
if (mx1+mx2>g)
{
cc(u,last);
return;
}
up[u]=mx1+last;
}
bool check(int l)
{
res.clear();
g=l;
selllll=0;
for1(i,1,n)
{
up[i]=0;
ed[i]=0;
}
dfs(1,0,0);
// cerr<< selllll<<'\n';
return (selllll<=k);
}
void sol()
{
cin >> n>> k;
for1(i,1,n-1)
{
int u,v,w;cin >> u>>v>>w;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
int l=0,r=1e14,mid;
while (l<=r)
{
//cerr<< l<<'\n';
mid=l+r>>1;
if (check(mid)) r=mid-1;
else l=mid+1;
}
cout << l;
cout << '\n';
check(l);
if (res.size()<k)
{
for1(i,1,n)
{
if (!ed[i]) res.pb(i);
if (res.size()==k) break;
}
}
for(int v: res) cout << v<<' ';
// cerr<< check(8);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;//cin >> t;
while(t--)
{
sol();
}
}
/*
6 3
2 1 7
3 1 2
3 4 6
1 5 9
1 6 6
*/
Compilation message
Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:53:20: warning: unused variable 'w' [-Wunused-variable]
53 | int v=x.fi,w=x.se;
| ^
Main.cpp: In function 'void sol()':
Main.cpp:113:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
113 | mid=l+r>>1;
| ~^~
Main.cpp:120:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
120 | if (res.size()<k)
| ~~~~~~~~~~^~
Main.cpp:125:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
125 | if (res.size()==k) break;
| ~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
27104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
232 ms |
28228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
