#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pi;
const ll INF = 1e18;
int n; ll k;
vector<pi> adj[300002];
bool chk[300002];
int ans = 0;
ll dfs(int x, int p, ll d)
{
vector<ll> v;
ll tmp1 = INF, tmp2 = 0;
ll D = INF; int t = 1;
for(auto u : adj[x])
{
int i = u.first;
if(i == p) continue;
ll c = u.second;
ll P = dfs(i, x, c);
if(P > 0 && P < tmp1)
{
tmp1 = P;
t = 1;
}
if(P < 0 && -P > tmp2)
{
tmp2 = -P;
t = -1;
}
}
if(tmp1 == INF && tmp2 == 0) { D = INF; }
else if(tmp1 == INF) { D = tmp2; t = -1; }
else if(tmp1 > tmp2) { D = tmp1; t = 1; }
else { D = tmp2; t = -1; }
if(D == INF)
{
if(d > k)
{
chk[x] = 1; ans++;
return 2*k+2;
}
return -(d+k+1);
}
if(D > k && D + d > 2*k+1)
{
chk[x] = 1; ans++;
return min(d, k+1);
}
else if(D > k) return t*(D+d);
if(D + d > k) return t*(k+1);
else return t*(D+d);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> k;
for(int i=1;i<n;i++)
{
int a, b; ll D; cin >> a >> b >> D;
adj[a].push_back({b, D});
adj[b].push_back({a, D});
}
ll P = dfs(1, 0, 0);
if(P < 0) P = -P;
if(P == 0) { chk[1] = 1; ans++; }
if(P > k) { chk[1] = 1; ans++; }
assert(ans <= n);
cout << ans << "\n";
for(int i=1;i<=n;i++) if(chk[i]) cout << i << " ";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
280 ms |
25540 KB |
Output is correct |
2 |
Correct |
274 ms |
25616 KB |
Output is correct |
3 |
Correct |
74 ms |
14020 KB |
Output is correct |
4 |
Correct |
265 ms |
25092 KB |
Output is correct |
5 |
Runtime error |
12 ms |
14668 KB |
Execution killed with signal 6 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
3 ms |
7244 KB |
Output is correct |
3 |
Correct |
3 ms |
7244 KB |
Output is correct |
4 |
Correct |
4 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
4 ms |
7244 KB |
Output is correct |
7 |
Correct |
4 ms |
7244 KB |
Output is correct |
8 |
Correct |
3 ms |
7244 KB |
Output is correct |
9 |
Incorrect |
4 ms |
7244 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
3 ms |
7244 KB |
Output is correct |
4 |
Correct |
3 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
4 ms |
7244 KB |
Output is correct |
7 |
Correct |
4 ms |
7292 KB |
Output is correct |
8 |
Correct |
4 ms |
7244 KB |
Output is correct |
9 |
Correct |
4 ms |
7244 KB |
Output is correct |
10 |
Correct |
3 ms |
7244 KB |
Output is correct |
11 |
Correct |
4 ms |
7244 KB |
Output is correct |
12 |
Correct |
4 ms |
7244 KB |
Output is correct |
13 |
Correct |
4 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7244 KB |
Output is correct |
15 |
Correct |
4 ms |
7244 KB |
Output is correct |
16 |
Incorrect |
4 ms |
7244 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
270 ms |
25660 KB |
Output is correct |
2 |
Incorrect |
118 ms |
17016 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
7460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
232 ms |
22988 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |