#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
const int MAXN = 1e5+5;
const int lgN = 17;
int N;
vector<ii> al[MAXN];
int S[MAXN], V[MAXN];
int p[MAXN];
int d[MAXN];
ll r[MAXN];
struct Line { int m; ll b; ll f(int x) { return (ll)m*x + b; } };
struct Hull {
Line v[MAXN];
int p[MAXN][lgN], vp;
Hull() { memset(p, -1, sizeof p); vp = 1; }
bool bad(Line a, Line b, Line c) {
return ((ll)c.b - b.b) * ((ll)a.m - b.m) <= ((ll)b.b - a.b) * ((ll)b.m - c.m); }
int add(Line l, int idx) {
RFOR(k,lgN-1,0) if (p[idx][k] != -1 and p[p[idx][k]][0] != -1
and bad(v[p[p[idx][k]][0]], v[p[idx][k]], l))
idx = p[idx][k];
if (p[idx][0] != -1 and bad(v[p[idx][0]], v[idx], l)) idx = p[idx][0];
v[vp] = l;
p[vp][0] = idx;
FOR(k,1,lgN-1) p[vp][k] = (p[vp][k-1] == -1 ? -1 : p[p[vp][k-1]][k-1]);
return vp++;
}
ll query(int x, int idx) {
RFOR(k,lgN-1,0) if (p[idx][k] != -1 and p[p[idx][k]][0] != -1
and v[p[p[idx][k]][0]].f(x) <= v[p[idx][k]].f(x))
idx = p[idx][k];
if (p[idx][0] != -1 and v[p[idx][0]].f(x) <= v[idx].f(x)) idx = p[idx][0];
return v[idx].f(x);
}
} ch;
void dfs(int u, int p, int pidx) {
r[u] = (ll)S[u] + (ll)V[u]*d[u];
//cout << u << " " << p[u] << endl;
//for (int v = p[u]; v != 0; v = p[v]) r[u] = min(r[u], (ll)S[u] + (ll)V[u]*(d[u]-d[v]) + r[v]);
if (u > 1) r[u] = min(r[u], ch.query(V[u], pidx) + (ll)S[u] + (ll)V[u]*d[u]);
int idx = ch.add({ -d[u], r[u] }, pidx);
for (auto v : al[u]) if (v.fi != p) {
d[v.fi] = d[u] + v.sc;
dfs(v.fi, u, idx);
}
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
FOR(i,1,N-1){
int u, v, d; cin >> u >> v >> d;
al[u].emplace_back(v, d);
al[v].emplace_back(u, d);
}
FOR(i,2,N){ cin >> S[i] >> V[i]; }
dfs(1,0,0);
FOR(i,2,N) cout << r[i] << (i == N ? '\n' : ' ');
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9336 KB |
Output is correct |
2 |
Correct |
12 ms |
9720 KB |
Output is correct |
3 |
Incorrect |
65 ms |
15864 KB |
Output isn't correct |
4 |
Correct |
109 ms |
18808 KB |
Output is correct |
5 |
Correct |
122 ms |
21752 KB |
Output is correct |
6 |
Correct |
149 ms |
24696 KB |
Output is correct |
7 |
Correct |
90 ms |
16888 KB |
Output is correct |
8 |
Correct |
186 ms |
20724 KB |
Output is correct |
9 |
Correct |
190 ms |
22296 KB |
Output is correct |
10 |
Correct |
165 ms |
21404 KB |
Output is correct |