#include<bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
typedef long double ll;
typedef pair <ll, ll> pii;
typedef pair <pii, ll> piii;
const int N = 1e5 + 7;
int n, siz;
ll a[N], b[N], dp[N], res[N];
vector <pii> adj[N];
pii v[N];
int ccw(pii x, pii y, pii z) {
return (x.F*(y.S-z.S) + y.F*(z.S-x.S) + z.F*(x.S-y.S) >= 0);
}
void DP(int x, int p, ll d) {
int lo = 0, hi = siz-1, poc = siz;
while (lo < hi) {
int mid = (lo + hi) / 2;
ll xx = v[mid].F * b[x] + v[mid].S, yy = v[mid+1].F * b[x] + v[mid+1].S;
if (xx > yy) lo = mid+1;
else hi = mid;
}
ll mn = 0;
if (siz) mn = v[lo].F * b[x] + v[lo].S;
mn += b[x]*d + a[x];
pii pp = {-d, mn};
lo = 1, hi = siz;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (ccw(v[mid-1], v[mid], pp)) hi = mid;
else lo = mid+1;
}
if (siz == 0) lo = 0;
pii po = v[lo];
v[lo] = pp;
siz = lo+1;
res[x] = mn;
for (auto it : adj[x]) {
if (it.F == p) continue;
DP(it.F, x, d + it.S);
}
siz--;
v[siz] = po;
siz = poc;
}
int main()
{
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
ll d; cin >> x >> y >> d;
adj[x].pb({y, d});
adj[y].pb({x, d});
}
for (int i = 2; i <= n; i++) {
cin >> a[i] >> b[i];
}
DP(1, 0, 0);
for (int i = 2; i <= n; i++) cout << res[i] << " ";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
2644 KB |
Output isn't correct |
2 |
Incorrect |
10 ms |
3328 KB |
Output isn't correct |
3 |
Incorrect |
158 ms |
13516 KB |
Output isn't correct |
4 |
Incorrect |
211 ms |
19440 KB |
Output isn't correct |
5 |
Incorrect |
339 ms |
24148 KB |
Output isn't correct |
6 |
Incorrect |
330 ms |
29464 KB |
Output isn't correct |
7 |
Incorrect |
270 ms |
15676 KB |
Output isn't correct |
8 |
Incorrect |
390 ms |
23236 KB |
Output isn't correct |
9 |
Incorrect |
369 ms |
25860 KB |
Output isn't correct |
10 |
Incorrect |
310 ms |
24224 KB |
Output isn't correct |