#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " <<
using namespace std;
const int N = 2e5+10,MOD = 998244353,inf = 2e12;
int n,k;
vector<pii> edges[N];
int up[N][20];
vi d(N);
vi leaves;
void dfs(int node,int p,int der = 0) {
if (node > 1 && edges[node].size() == 1) leaves.push_back(node);
up[node][0] = p;
d[node] = der;
for (int i = 1;i<20;i++) up[node][i] = up[up[node][i-1]][i-1];
for (auto it : edges[node]) {
if (it.ff == p) continue;
dfs(it.ff,node,der+it.ss);
}
}
vi active(N,1),usedd(N,0);
vi anss;
int find(int node,int k) {
int cur = node;
for (int i = 19;i>=0;i--) {
if (d[node]-d[up[cur][i]] <= k && active[up[cur][i]]) cur = up[cur][i];
}
return cur;
}
bool check(int dep,bool construct = 0) {
active.assign(n+1,1);
int used = 0;
priority_queue<pii> pq;
for (auto it : leaves) {
int gogo = find(it,dep);
pq.push({d[gogo],gogo});
}
while (!pq.empty()) {
int f = pq.top().ss;
pq.pop();
if (!active[f]) continue;
if (construct) anss.push_back(f),usedd[f] = 1;
used++;
queue<pii> q;
q.push({f,0});
active[f] = 0;
while (!q.empty()) {
int tp = q.front().ff,c = q.front().ss;
q.pop();
for (auto it : edges[tp]) {
if (it.ss+c > dep) continue;
if (!active[it.ff]) continue;
active[it.ff] = 0;
q.push({it.ff,c+it.ss});
}
}
int gogo = find(f,dep);
if (d[f]-d[up[gogo][0]] > dep) pq.push({d[up[gogo][0]],up[gogo][0]});
}
if (construct) {
for (int i=1;i<=n;i++) {
if (!usedd[i] && anss.size() < k) anss.push_back(i);
}
}
return used <= k;
}
void solve() {
cin >> n >> k;
for (int i=1;i<n;i++) {
int a,b,w;
cin >> a >> b >> w;
edges[a].push_back({b,w});
edges[b].push_back({a,w});
}
dfs(1,1);
int l = 0;
int r = 1e15;
while (l<=r) {
int m = (l+r) >> 1;
if (check(m)) r = m-1;
else l = m+1;
}
cout << l << '\n';
check(l,1);
sort(all(anss));
for (auto it : anss) cout << it << ' ';
cout << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
# | 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... |