#include <bits/stdc++.h>
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
using namespace std;
using ll = long long;
struct line {
ll a, b;
line(ll a_, ll b_) : a(a_), b(b_) {}
line() : a(0LL), b(0LL) {}
ll operator()(ll x) const {
return a * x + b;
}
};
ll floor_div(ll a, ll b) {
return a / b - ((a ^ b) < 0 && a % b);
}
ll intersect(const line& l1, const line& l2) {
return floor_div(l2.b - l1.b, l1.a - l2.a);
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int N;
cin >> N;
vector<vector<pair<int, ll>>> adj(N+1);
for (int i = 0; i < N-1; i++) {
int U, V, D;
cin >> U >> V >> D;
assert(D > 0);
adj[U].emplace_back(V, (ll)D);
adj[V].emplace_back(U, (ll)D);
}
vector<ll> S(N+1), V(N+1);
for (int i = 2; i <= N; i++) {
cin >> S[i] >> V[i];
}
vector<ll> dp(N+1);
vector<line> st(N+2);
int p = 1;
auto dfs = y_combinator([&](auto self, int u, int parent, ll dist) -> void {
if (u == 1) {
for (auto [v, w] : adj[u]) {
if (v != parent) {
self(v, u, dist+w);
}
}
return;
}
int lo = 0, hi = p - 1;
ll x = V[u];
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (intersect(st[mid-1], st[mid]) < x) lo = mid;
else hi = mid - 1;
}
dp[u] = S[u] + V[u] * dist - st[lo](x);
line cur(dist, -dp[u]);
lo = 1, hi = p;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (intersect(cur, st[mid]) <= intersect(st[mid], st[mid-1])) {
hi = mid;
} else {
lo = mid + 1;
}
}
auto prev_line = st[lo];
int prev_p = p;
st[lo] = cur;
p = lo + 1;
for (auto [v, w] : adj[u]) {
if (v != parent) {
self(v, u, dist+w);
}
}
st[lo] = prev_line;
p = prev_p;
});
dfs(1, 1, 0);
for (int i = 2; i <= N; i++) {
cout << dp[i] << " \n"[i == N];
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
51 ms |
10500 KB |
Output is correct |
4 |
Correct |
71 ms |
15500 KB |
Output is correct |
5 |
Correct |
79 ms |
20264 KB |
Output is correct |
6 |
Correct |
122 ms |
25128 KB |
Output is correct |
7 |
Correct |
54 ms |
12004 KB |
Output is correct |
8 |
Correct |
117 ms |
18072 KB |
Output is correct |
9 |
Correct |
128 ms |
20152 KB |
Output is correct |
10 |
Correct |
100 ms |
18720 KB |
Output is correct |