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 endl "\n"
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 5;
constexpr int INF = 1e18;
int n,k;
vector<array<int,2>> v[N];
bool ok=1;
int vis[N];
int dp[N];
int depth[N];
int maxi[N];
int ck;
void dfs(int c,int p,int d){
if(!ok) return;
depth[c]=d;
maxi[c]=d;
for(array<int,2> x:v[c]){
int u=x[0],co=x[1];
if(u==p) continue;
dfs(u,c,d+co);
dp[c]=min(dp[c],dp[u]);
maxi[c]=max(maxi[c],maxi[u]);
}
if(maxi[c]<=ck+2*d-dp[c]) {
maxi[c]=-INF;
return;
}
int u = maxi[c];
if(u>ck+d){
ok=0;
return;
}
if(c==1){
vis[c]=1;
dp[c]=d;
maxi[c]=-INF;
return;
}
if(u-depth[p]>ck){
vis[c]=1;
dp[c]=d;
maxi[c]=-INF;
return;
}
}
bool check(int x){
ok=1;
fill(dp,dp+N,INF);
fill(vis,vis+N,0);
fill(maxi,maxi+N,-INF);
ck=x;
dfs(1,0,0);
if(ok && count(vis,vis+N,1)<=k) return 1;
return 0;
}
void solve(){
cin >> n >> k;
for(int i=1;i<n;i++){
int a,b,c;
cin >> a >> b >> c;
v[a].pb({b,c});
v[b].pb({a,c});
}
int l=0,r=(int)1e15;
while(l<r){
int m=(l+r)/2;
if(check(m)) r=m;
else l=m+1;
}
cout << l << endl;
check(l);
vector<int> ans;
for(int i=1;i<=n;i++) if(vis[i]) ans.pb(i);
for(int i=1;i<=n;i++) if(!vis[i] && sz(ans)<k) ans.pb(i);
for(int x:ans) cout << x << " ";
cout << endl;
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int t=1;//cin >> t;
while(t--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |