#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second
void solution();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solution();
return 0;
}
const int N = 3e5+10;
vector<pr> adj[N];
ll sz[N];
bool vis[N];
bool safe[N];
ll n, k;
vi res;
ll get_sz(int a, int p) {
sz[a] = 0;
for (auto [b, w] : adj[a]) {
if (vis[b] || safe[b] || b == p) continue;
sz[a] += w + get_sz(b, a);
}
return sz[a];
}
int centroid(int a, int p, ll l) {
for (auto [b, w] : adj[a]) {
if (!vis[b] && !safe[b] && b != p && sz[b]*2 > l)
return centroid(b, a, l);
}
return a;
}
void add_safe(int a, int p, ll d) {
if (d > k) return;
safe[a] = true;
for (auto [b, w] : adj[a]) {
if (vis[b] || safe[b] || b == p) continue;
add_safe(b, a, d+w);
}
}
void solve(int a, int p) {
int c = centroid(a, p, get_sz(a, p));
vis[c] = true;
if (!safe[c]) {
res.push_back(c);
safe[c] = true;
for (auto [b, w] : adj[c]) {
if (vis[b] || safe[b]) continue;
add_safe(b, c, w);
}
}
for (auto [b, w] : adj[c]) {
if (vis[b]) continue;
solve(b, c);
}
}
void solution() {
cin >> n >> k;
for (int i = 1; i < n; i++) {
ll a, b, w;
cin >> a >> b >> w;
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
solve(1, 1);
cout << res.size() << endl;
for (auto val : res) cout << val << " ";
}
| # | 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... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |