#include <bits/stdc++.h>
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=1e9+11;
const ll lnf=1e15+11;
using pll=pair<ll,ll>;
using vp=vec(pll);
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});
}
vi pns;
int cnt=0;
vec(pair<int,pll>) cands;
auto dfs=[&](auto self,int v,int par,int can)->pll{
pll now={0,-lnf};
cands.clear();
for(auto e:adj[v]){
auto [u,w]=e;
if(u==par) continue;
pll nep=self(self,u,v,can);
if(nep.fi+w>can){
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});
}
}
for(auto tp:cands){
ll w=tp.fi;
pll p=tp.se;
now.fi=max(now.fi,p.fi+w);
}
if(now.fi<=now.se){
now.fi=-lnf;
}
return now;
};
auto quq=[&](int x)->bool{
cnt=0;
pns.clear();
pll p=dfs(dfs,0,-1,x);
if(p.fi!=-lnf){
cnt+=1;
pns.pb(0);
}
return cnt<=k;
// print("\n...",cnt);
};
ll c;
{
ll l=1,r=lnf;
while(l<=r){
ll m=(l+r)>>1;
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 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3090 ms |
46888 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
570 ms |
47724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
