#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 long 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 ((long double) x.F*(y.S-z.S) + (long double) y.F*(z.S-x.S) + (long double) 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 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3028 KB |
Output is correct |
| 3 |
Correct |
82 ms |
10188 KB |
Output is correct |
| 4 |
Correct |
115 ms |
13892 KB |
Output is correct |
| 5 |
Correct |
157 ms |
17064 KB |
Output is correct |
| 6 |
Correct |
184 ms |
20280 KB |
Output is correct |
| 7 |
Correct |
115 ms |
10828 KB |
Output is correct |
| 8 |
Correct |
206 ms |
15892 KB |
Output is correct |
| 9 |
Correct |
187 ms |
17572 KB |
Output is correct |
| 10 |
Correct |
182 ms |
16272 KB |
Output is correct |
