#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;
struct Line {
ll m, b;
ll eval(ll x) {
return m * x + b;
}
};
int n, x[N], y[N];
ll depth[N], dp[N];
vector<ar<int, 2>> adj[N];
Line hull[N];
int k = 0;
ll qry(ll x) {
int lo = 0, hi = k, mid = (lo + hi) / 2;
while (lo < mid && mid < hi) {
// intersection of hull[mid] and hull[mid-1] <= x
Line A = hull[mid-1];
Line B = hull[mid];
// (B.b - A.b) / (A.m - B.m) <= x
if ((B.b - A.b) <= x * (A.m - B.m)) lo = mid;
else hi = mid;
mid = (lo + hi) / 2;
}
return hull[lo].eval(x);
}
bool better(Line cur, int i) {
// true iff intersection point between (i-1, cur) <= (i-1, i)
Line A = hull[i-1];
Line B = hull[i];
// (cur.b - A.b) / (A.m - cur.m) <= (B.b - A.b) / (A.m - B.m)
return (cur.b - A.b) * (A.m - B.m) <= (B.b - A.b) * (A.m - cur.m);
}
void dfs(int c, int p) {
// x[c] + (depth[c] - depth[nxt]) * y[c] + dp[nxt]
// insert {-depth[nxt], dp[nxt]}
// query y[c]
//
// as you insert, slopes are decreasing
if (p != -1) {
dp[c] = qry(y[c]);
dp[c] += x[c] + depth[c] * y[c];
}
int base_k = k;
pair<int, Line> change{-1, Line{-1, -1}};
// insert {-depth[nxt], dp[nxt]}
Line cur = Line{-depth[c], dp[c]};
if (k >= 2) {
int lo = 0, hi = k, mid = (lo + hi) / 2;
while (lo < mid && mid < hi) {
if (better(cur, mid)) hi = mid;
else lo = mid;
mid = (lo + hi) / 2;
}
if (hi == k) { // don't delete anything
change = make_pair(k, hull[k]);
hull[k++] = cur;
} else {
change = make_pair(hi, hull[hi]);
hull[hi] = cur;
k = hi+1;
}
} else {
change = make_pair(k, hull[k]);
hull[k++] = cur;
}
for (auto [nxt, w] : adj[c]) if (nxt != p) {
depth[nxt] = depth[c] + w;
dfs(nxt, c);
}
k = base_k;
hull[change.first] = change.second;
}
void solve() {
cin >> n;
for (int i = 0; i < n-1; i++) {
int a, b, w; cin >> a >> b >> w, --a, --b;
adj[a].push_back({b, w}), adj[b].push_back({a, w});
}
for (int i = 1; i < n; i++) {
cin >> x[i] >> y[i];
}
dfs(0, -1);
for (int i = 1; i < n; i++) {
cout << dp[i] << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7852 KB |
Output is correct |
3 |
Incorrect |
33 ms |
15860 KB |
Output isn't correct |
4 |
Correct |
61 ms |
19884 KB |
Output is correct |
5 |
Correct |
56 ms |
23556 KB |
Output is correct |
6 |
Correct |
75 ms |
27076 KB |
Output is correct |
7 |
Correct |
43 ms |
16624 KB |
Output is correct |
8 |
Incorrect |
80 ms |
21844 KB |
Output isn't correct |
9 |
Correct |
104 ms |
24276 KB |
Output is correct |
10 |
Correct |
75 ms |
22748 KB |
Output is correct |