#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pi;
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;
int cnt = 0;
for(auto u : adj[x])
{
int i = u.first;
if(i == p) continue;
ll c = u.second;
ll P = dfs(i, x, c);
v.push_back(P);
}
sort(v.begin(), v.end());
if(v.empty())
{
if(d > k)
{
chk[x] = 1; ans++;
return 2*k+2;
}
return -(d+k+1);
}
else
{
ll D = v[0];
int t = 1;
if(D < 0) { t = -1; D = -D; }
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++; }
cout << ans << "\n";
for(int i=1;i<=n;i++) if(chk[i]) cout << i << " ";
}
Compilation message
Firefighting.cpp: In function 'll dfs(int, int, ll)':
Firefighting.cpp:15:9: warning: unused variable 'cnt' [-Wunused-variable]
15 | int cnt = 0;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
279 ms |
25676 KB |
Output is correct |
2 |
Correct |
306 ms |
25620 KB |
Output is correct |
3 |
Correct |
83 ms |
14140 KB |
Output is correct |
4 |
Correct |
271 ms |
25244 KB |
Output is correct |
5 |
Incorrect |
4 ms |
7244 KB |
Integer parameter [name=F] equals to 3, violates the range [1, 2] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
4 ms |
7240 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 |
6 ms |
7244 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 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 |
7292 KB |
Output is correct |
8 |
Correct |
5 ms |
7244 KB |
Output is correct |
9 |
Correct |
5 ms |
7244 KB |
Output is correct |
10 |
Correct |
4 ms |
7244 KB |
Output is correct |
11 |
Correct |
5 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 |
5 ms |
7360 KB |
Output is correct |
15 |
Correct |
4 ms |
7244 KB |
Output is correct |
16 |
Incorrect |
5 ms |
7244 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
304 ms |
25616 KB |
Output is correct |
2 |
Incorrect |
151 ms |
17044 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
7500 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
277 ms |
23068 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |