// 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, INFL);
cout << sz(ans) << nl;
for(auto& x : ans) cout << x + 1 << " ";
cout << nl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
182 ms |
21644 KB |
Output is correct |
2 |
Correct |
174 ms |
21636 KB |
Output is correct |
3 |
Correct |
45 ms |
8260 KB |
Output is correct |
4 |
Correct |
164 ms |
21040 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 |
224 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 |
1 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 |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
216 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
171 ms |
21636 KB |
Output is correct |
2 |
Correct |
66 ms |
11528 KB |
Output is correct |
3 |
Correct |
70 ms |
11768 KB |
Output is correct |
4 |
Correct |
56 ms |
10280 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
125 ms |
20444 KB |
Output is correct |
8 |
Correct |
125 ms |
20484 KB |
Output is correct |
9 |
Correct |
124 ms |
20500 KB |
Output is correct |
10 |
Correct |
132 ms |
20540 KB |
Output is correct |
11 |
Correct |
201 ms |
21660 KB |
Output is correct |
12 |
Correct |
89 ms |
14152 KB |
Output is correct |
13 |
Correct |
46 ms |
9008 KB |
Output is correct |
14 |
Correct |
79 ms |
13332 KB |
Output is correct |
15 |
Correct |
104 ms |
16028 KB |
Output is correct |
16 |
Correct |
117 ms |
17136 KB |
Output is correct |
17 |
Correct |
115 ms |
14520 KB |
Output is correct |
18 |
Correct |
110 ms |
14304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
592 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
536 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
15 |
Correct |
2 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
143 ms |
17844 KB |
Output is correct |
2 |
Correct |
124 ms |
16924 KB |
Output is correct |
3 |
Correct |
147 ms |
18300 KB |
Output is correct |
4 |
Correct |
51 ms |
8628 KB |
Output is correct |
5 |
Correct |
170 ms |
32992 KB |
Output is correct |
6 |
Correct |
163 ms |
31152 KB |
Output is correct |
7 |
Correct |
165 ms |
36804 KB |
Output is correct |
8 |
Correct |
185 ms |
35520 KB |
Output is correct |
9 |
Correct |
166 ms |
28780 KB |
Output is correct |
10 |
Correct |
168 ms |
27752 KB |
Output is correct |
11 |
Correct |
223 ms |
38184 KB |
Output is correct |
12 |
Correct |
90 ms |
12388 KB |
Output is correct |
13 |
Correct |
179 ms |
30168 KB |
Output is correct |
14 |
Correct |
236 ms |
25556 KB |
Output is correct |
15 |
Correct |
185 ms |
18516 KB |
Output is correct |
16 |
Correct |
202 ms |
17228 KB |
Output is correct |
17 |
Correct |
155 ms |
17200 KB |
Output is correct |
18 |
Correct |
198 ms |
18344 KB |
Output is correct |
19 |
Correct |
132 ms |
12900 KB |
Output is correct |
20 |
Correct |
56 ms |
7536 KB |
Output is correct |
21 |
Correct |
187 ms |
18376 KB |
Output is correct |