# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
825840 | karrigan | Parkovi (COCI22_parkovi) | 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.
#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],select;
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;
select++;
}
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;
select=0;
for1(i,1,n)
{
up[i]=0;
ed[i]=0;
}
dfs(1,0,0);
// cerr<< select<<'\n';
return (select<=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
*/