#include <bits/stdc++.h>
#define X first
#define Y second
#define ll long long
#define MP make_pair
using namespace std;
const int N = 1e5 + 123;
const ll INF = 1e18;
typedef pair<ll, ll> Line;
ll f(Line me, ll x) {
return me.X * x + me.Y;
}
int CHT[N], n, sz;
vector< pair<int, ll> > g[N];
ll dp[N], d[N], sp[N], sl[N];
Line cf[N];
ll get(ll x) {
int l = 1, r = sz - 1;
while(l <= r) {
int m = (l + r) / 2;
if(f(cf[CHT[m]], x) < f(cf[CHT[m + 1]], x))
r = m - 1;
else
l = m + 1;
}
return f(cf[CHT[r + 1]], x);
}
bool bad(int x, int y, int z) {
return (cf[x].Y - cf[y].Y) * 1.0 / (cf[y].X - cf[x].X) >= (cf[x].Y - cf[z].Y) * 1.0 / (cf[z].X - cf[x].X);
}
void dfs(int v, int pr) {
if(pr != -1) {
dp[v] = get(sp[v]) + sl[v] + sp[v] * d[v];
}
cf[v] = {-d[v], dp[v]};
int l = 2, r = sz;
while(l <= r) {
int m = (l + r) / 2;
if(bad(CHT[m - 1], CHT[m], v))
r = m - 1;
else
l = m + 1;
}
int bfr = CHT[r + 1];
int bfr_sz = sz;
sz = r + 1, CHT[r + 1] = v;
for(pair<int, ll> to: g[v]) {
if(to.X == pr) continue;
d[to.X] = d[v] + to.Y, dfs(to.X, v);
}
sz = bfr_sz, CHT[r + 1] = bfr;
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1, x, y, z;i < n;i++) {
cin >> x >> y >> z;
g[x].push_back({y, z});
g[y].push_back({x, z});
}
for(int i = 2;i <= n;i++)
cin >> sl[i] >> sp[i];
dfs(1, -1);
for(int i = 2;i <= n;i++)
cout << dp[i] << " ";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3148 KB |
Output is correct |
| 3 |
Correct |
53 ms |
10948 KB |
Output is correct |
| 4 |
Correct |
76 ms |
15044 KB |
Output is correct |
| 5 |
Correct |
107 ms |
19036 KB |
Output is correct |
| 6 |
Correct |
122 ms |
22748 KB |
Output is correct |
| 7 |
Correct |
68 ms |
12456 KB |
Output is correct |
| 8 |
Correct |
139 ms |
17828 KB |
Output is correct |
| 9 |
Correct |
148 ms |
19348 KB |
Output is correct |
| 10 |
Correct |
121 ms |
18108 KB |
Output is correct |
