// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
using db = long double;
const int MOD = 1e9 + 7;
const ll INFL = ll(1e16) + 10;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N; ll K; cin >> N >> K;
V<vpi> adj(N); for(int i = 0; i < N-1; i++) {
int u, v, w; cin >> u >> v >> w; --u, --v;
adj[u].pb(mp(v, w));
adj[v].pb(mp(u, w));
}
vi ans;
function<pl(int, int, ll)> dfs = [&](int u, int p, ll d) {
ll close = -INFL, far = 0;
for(auto& e : adj[u]) {
auto [v, w] = e; if (v == p) continue;
pl R = dfs(v, u, w);
if (R.f) {
close = max(close, R.s);
} else {
far = max(far, R.s);
}
}
pl R;
if (close >= far) {
R = mp(1, close - d);
} else {
R = mp(0, far + d);
}
if (R.f && R.s < 0) R = mp(0, 0);
if (!R.f && R.s > K) {
ans.pb(u); R = mp(1, K - d);
}
return R;
};
dfs(0, -1, MOD);
cout << sz(ans) << nl;
for(auto& x : ans) cout << x + 1 << " ";
cout << nl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
21612 KB |
Output is correct |
| 2 |
Correct |
202 ms |
21752 KB |
Output is correct |
| 3 |
Correct |
52 ms |
8256 KB |
Output is correct |
| 4 |
Correct |
172 ms |
21076 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
316 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
324 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
316 KB |
Output is correct |
| 23 |
Correct |
0 ms |
324 KB |
Output is correct |
| 24 |
Correct |
0 ms |
316 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
21640 KB |
Output is correct |
| 2 |
Correct |
100 ms |
11536 KB |
Output is correct |
| 3 |
Correct |
80 ms |
14524 KB |
Output is correct |
| 4 |
Correct |
76 ms |
12612 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
125 ms |
25384 KB |
Output is correct |
| 8 |
Correct |
129 ms |
25156 KB |
Output is correct |
| 9 |
Correct |
125 ms |
25344 KB |
Output is correct |
| 10 |
Correct |
130 ms |
25316 KB |
Output is correct |
| 11 |
Correct |
241 ms |
28476 KB |
Output is correct |
| 12 |
Correct |
93 ms |
17376 KB |
Output is correct |
| 13 |
Correct |
55 ms |
10936 KB |
Output is correct |
| 14 |
Correct |
80 ms |
16460 KB |
Output is correct |
| 15 |
Correct |
108 ms |
19760 KB |
Output is correct |
| 16 |
Correct |
150 ms |
21200 KB |
Output is correct |
| 17 |
Correct |
98 ms |
17976 KB |
Output is correct |
| 18 |
Correct |
106 ms |
17508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Integer parameter [name=F] equals to 0, violates the range [1, 2576] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
17792 KB |
Output is correct |
| 2 |
Incorrect |
137 ms |
16956 KB |
Integer parameter [name=F] equals to 0, violates the range [1, 276153] |
| 3 |
Halted |
0 ms |
0 KB |
- |
