#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]};
stack<int> his;
while(sz > 1 && bad(CHT[sz - 1], CHT[sz], v))
his.push(CHT[sz--]);
CHT[++sz] = 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--;
while(!his.empty())
CHT[++sz] = his.top(), his.pop();
}
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 |
5 ms |
4872 KB |
Output is correct |
| 3 |
Runtime error |
71 ms |
39952 KB |
Memory limit exceeded |
| 4 |
Runtime error |
107 ms |
58004 KB |
Memory limit exceeded |
| 5 |
Runtime error |
114 ms |
65540 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
131 ms |
65540 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
90 ms |
32944 KB |
Memory limit exceeded |
| 8 |
Execution timed out |
1093 ms |
46604 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1094 ms |
30016 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1090 ms |
53864 KB |
Time limit exceeded |
