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
#pragma GCC optimize ("O3")
#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];
multiset<int> s[N];
int ck;
inline void dfs(int c,int p,int d){
if(!ok) return;
depth[c]=d;
s[c].clear();
s[c].insert(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]);
if(sz(s[c])<sz(s[u])) swap(s[c],s[u]);
for(int y:s[u]) s[c].insert(y);
}
while(!s[c].empty()){
if(*s[c].begin() <= ck + 2*d - dp[c]) s[c].erase(s[c].find(*s[c].begin()));
else break;
}
if(s[c].empty()) return;
int u = *s[c].rbegin();
if(u>ck+d){
ok=0;
return;
}
if(c==1){
vis[c]=1;
dp[c]=d;
s[c].clear();
return;
}
if(u-depth[p]>ck){
vis[c]=1;
dp[c]=d;
s[c].clear();
return;
}
}
inline bool check(int x){
ok=1;
fill(dp,dp+N,INF);
fill(vis,vis+N,0);
ck=x;
dfs(1,0,0);
if(s[1].empty() && 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... |