#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second
#define sz(a) a.size()
#define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--))
#define mnto(x,y) x = min(x, (__typeof__(x))y)
#define mxto(x,y) x = max(x, (__typeof__(x))y)
int n;
ll k;
vi ans;
vector<pii> adj[300005];
pair<bool, ll> dfs(int idx, int p, ll d) {
// mo is max distance from station child
// mu is max distance from no-station child
ll mo = LLONG_MIN, mu = 0;
for (pii &pr : adj[idx]) {
if (pr.fr != p) {
pair<bool, ll> res = dfs(pr.fr, idx, pr.sc);
if (res.fr) mxto(mo, res.sc);
else mxto(mu, res.sc);
}
}
pair<bool, ll> si;
if (mo >= mu) si = {1, mo-d};
else si = {0, mu+d};
if (!si.fr && si.sc > k) {
ans.pb(idx);
si = {1, k-d};
}
if (si.fr && si.sc < 0) si = {0, 0};
return si;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
rep(i, 1, n) {
int a, b, w;
cin >> a >> b >> w;
a--; b--;
adj[a].eb(b, w);
adj[b].eb(a, w);
}
dfs(0, -1, LLONG_MAX/4);
cout << sz(ans) << '\n';
rep(i, 0, sz(ans)) cout << ans[i]+1 << ' ';
}
| # | 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... |