#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
const ll MAXI = 1e9;
struct line {
ll dalj, b, cf;
line() : dalj(0), b(0), cf(0) {};
line(ll dalj, ll b, ll cf) : dalj(dalj), b(b), cf(cf) {};
ll calc(ll d, ll s, ll v) {
return (d-dalj)*v+s+b;
}
};
const int N = 1e5+11;
pair <ll, ll> a[N]; // a[i].ff = v; a[i].ss = s;
vector <pair<int, ll> > ls[N];
int n;
ll dist[N];
ll res[N];
line c[N];
int p[20][N]; // da znamo na kog ide nasa linija
bool pojede(line x, line y) { // pojede li linija x s manjim a-om y ili ne
// x ima manji a, veci dalj
if (x.b <= y.b) return 1;
if (y.cf*(x.dalj-y.dalj) >= x.b-y.b) return 1;
return 0;
}
int sjeciste(line x, line y) {
double ret = x.b-y.b;
ret /= (x.dalj-y.dalj);
return ceil(ret);
}
void dfs(int x, int roditelj, ll d, int prev) {
dist[x] = d;
c[x].dalj = d; c[x].b = d*a[x].ff+a[x].ss; c[x].cf = 0;
res[x] = c[x].b;
if (prev == 0) {
for (auto susj : ls[x]) {
if (susj.ff == roditelj) continue;
dfs(susj.ff, x, d+susj.ss, x);
}
return;
}
int rj = prev;
ll brzina = a[x].ff;
for (int i=19;i>=0;i--) {
if (p[i][rj] == 0) continue;
if (c[p[i][rj]].cf > brzina) rj = p[i][rj];
}
if (c[rj].cf > brzina) rj = p[0][rj];
res[x] = min(res[x], c[rj].calc(d, a[x].ss, a[x].ff));
c[x].b = res[x];
int spoji = prev;
for (int i=19;i>=0;i--) {
if (p[i][spoji] == 0) continue;
if (pojede(c[x], c[p[i][spoji]])) spoji = p[i][spoji];
}
if (pojede(c[x], c[spoji])) spoji = p[0][spoji];
if (spoji == 0) {
for (auto susj : ls[x]) {
if (susj.ff == roditelj) continue;
dfs(susj.ff, x, d+susj.ss, x);
}
return;
}
p[0][x] = spoji;
for (int i=1;i<20;i++) p[i][x] = p[i-1][p[i-1][x]];
c[x].cf = sjeciste(c[x], c[p[0][x]]);
prev = x;
if (c[x].cf > MAXI) prev = p[0][x];
for (auto susj : ls[x]) {
if (susj.ff == roditelj) continue;
dfs(susj.ff, x, d+susj.ss, prev);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i=0;i<n-1;i++) {
int a1, a2;
ll c1;
cin >> a1 >> a2 >> c1; a1--; a2--;
ls[a1].pb(mp(a2, c1));
ls[a2].pb(mp(a1, c1));
}
for (int i=1;i<n;i++) {
cin >> a[i].ss >> a[i].ff;
}
dfs(0, 0, 0, 0);
for (int i=1;i<n;i++) cout << res[i] << " ";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5868 KB |
Output is correct |
| 3 |
Correct |
80 ms |
16108 KB |
Output is correct |
| 4 |
Correct |
116 ms |
21228 KB |
Output is correct |
| 5 |
Correct |
135 ms |
26428 KB |
Output is correct |
| 6 |
Correct |
164 ms |
31452 KB |
Output is correct |
| 7 |
Correct |
106 ms |
19308 KB |
Output is correct |
| 8 |
Correct |
277 ms |
26280 KB |
Output is correct |
| 9 |
Correct |
236 ms |
27872 KB |
Output is correct |
| 10 |
Correct |
210 ms |
26596 KB |
Output is correct |
