#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3ulnVOy ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<"\n";}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
const int inf=1e18+11;
using vp=vec(pii);
signed main(){
_3ulnVOy;
int n,k;
cin>>n>>k;
vec(vp) adj(n);
rep(i,n-1){
int u,v,w;
cin>>u>>v>>w;
u-=1,v-=1;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
int cnt=0;
vi pns;
auto dfs=[&](auto self,int v,int par,int can)->pii{
pii now={0,-inf};
// distance to farthest node with no red node being near
// distance to red node
vec(pair<int,pii>) cands;
for(auto e:adj[v]){
auto [u,w]=e;
if(u==par) continue;
pii nep=self(self,u,v,can);
// {
// if(v==3){
// print(nep.fi+w,nep.se);
// }
// }
if(nep.fi+w>can){
// print(v,u,nep.fi);
pns.pb(u);
now.se=max(now.se,can-w);
cnt+=1;
}else{
now.se=max(now.se,nep.se-w);
cands.pb({w,nep});
}
}
// if(v==2) print(now.fi,now.se);
for(auto tp:cands){
pii nep=tp.se;
int w=tp.fi;
if(nep.fi+w<=now.se){
continue;
}
now.fi=max(now.fi,nep.fi+w);
}
if(now.se>=0){
now.fi=-inf;
}
// if(v==1) print(now.fi,now.se);
return now;
};
auto quq=[&](int x)->bool{
cnt=0;
pns.clear();
pii p=dfs(dfs,0,-1,x);
if(p.fi>0){
cnt+=1;
pns.pb(0);
}
return cnt<=k;
// print("\n...",cnt);
};
// quq(3);
int l=1,r=inf,c=-1;
while(l<=r){
int m=(l+r)/2;
if(quq(m)){
c=m;
r=m-1;
}else{
l=m+1;
}
}
quq(c);
{
vi usd(n,0);
rep(i,sz(pns)){
usd[pns[i]]=1;
}
rep(i,n){
if(!usd[i] and sz(pns)<k){
pns.pb(i);
}
}
}
print(c);
for(auto v:pns){
cout<<v+1<<" ";
}
print();
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
844 ms |
53092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
873 ms |
55556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
