This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 300010;
const int INF = LLONG_MAX/3;
int n,k;
vector <pi> adjlist[maxn];
vector <int> ans;
int dfs(int x, int p, int d) {
int maxover = -INF, minunder = 0;
for (auto i: adjlist[x]) if (i.f != p) {
int res = dfs(i.f,x,i.s);
if (res < 0) minunder = min(minunder,res);
else if (res > 0) maxover = max(maxover,res - i.s);
}
int res = 0;
if (maxover < abs(minunder)) {
if (abs(minunder) + d <= k) { //delay. Underflow
res = -(abs(minunder) + d);
} else { //Build here. overflow.
ans.push_back(x);
res = k;
}
} else if (maxover >= abs(minunder)) {
res = maxover;
}
return res;
}
int32_t main() {
FAST
cin >> n >> k;
for (int i =0;i<n-1;i++) {
int a,b,d; cin >> a >> b >> d;
adjlist[a].push_back(pi(b,d));
adjlist[b].push_back(pi(a,d));
}
dfs(1,-1,INF);
cout << ans.size() << "\n";
for (auto i: ans) cout << i << " ";
}
# | 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... |