#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;
using T = tuple<int, i64, i64>;
int n, r;
vector<vector<ii>> g;
vector<i64> pre, dp;
stack<T> changes;
vector<pair<i64, i64>> dq;
vector<int> s, vel;
ld point(i64 a0, i64 b0, i64 a1, i64 b1) {
return (b1 - b0) / ld(a0 - a1);
}
void dfs(int u, int p) {
if(u != p) {
int lo = 1, hi = r - 1;
while(lo < hi) {
int mid = (lo + hi) / 2;
auto [a0, b0] = dq[mid - 1];
auto [a1, b1] = dq[mid];
if((b1 - b0) > (a0 - a1) * vel[u]) hi = mid;
else lo = mid + 1;
}
hi = max(0, hi - 1);
dp[u] = s[u] + vel[u] * (pre[u] + dq[hi].first) + dq[hi].second;
}
while((int)dq.size() >= 2) {
int n = dq.size();
auto [a0, b0] = dq[n - 1];
auto [a1, b1] = dq[n - 2];
if(point(-pre[u], dp[u], a0, b0) > point(a0, b0, a1, b1)) break;
changes.emplace(u, a0, b0);
dq.pop_back();
}
dq[r++] = {-pre[u], dp[u]};
for(auto [v, d] : g[u]) {
if(v == p) continue;
pre[v] = pre[u] + d;
dfs(v, u);
}
--r;
while(!changes.empty()) {
auto [_, a, b] = changes.top();
if(_ != u) break;
changes.pop();
dq[r++] = {a, b};
}
}
void solve() {
cin >> n;
g.resize(n);
pre.resize(n);
dp.resize(n);
s.resize(n);
vel.resize(n);
dq.resize(n);
for(int i = 1; i < n; ++i) {
int u, v, d;
cin >> u >> v >> d;
--u, --v;
g[u].emplace_back(v, d);
g[v].emplace_back(u, d);
}
s[0] = vel[0] = 0;
for(int i = 1; i < n; ++i) cin >> s[i] >> vel[i];
pre[0] = dp[0] = 0;
dfs(0, 0);
for(int i = 1; i < n; ++i) cout << dp[i] << ' ';
cout << '\n';
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Incorrect |
2 ms |
916 KB |
Output isn't correct |
3 |
Incorrect |
39 ms |
9796 KB |
Output isn't correct |
4 |
Incorrect |
55 ms |
14452 KB |
Output isn't correct |
5 |
Incorrect |
77 ms |
18944 KB |
Output isn't correct |
6 |
Incorrect |
109 ms |
23148 KB |
Output isn't correct |
7 |
Incorrect |
72 ms |
12644 KB |
Output isn't correct |
8 |
Incorrect |
110 ms |
18060 KB |
Output isn't correct |
9 |
Incorrect |
89 ms |
19856 KB |
Output isn't correct |
10 |
Incorrect |
75 ms |
19008 KB |
Output isn't correct |