#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[sz(V)-2])
#define allv(V) ((V).begin()),((V).end())
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll operator * (const pll &a, const pll &b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll &a, const pll &b, const pll &c) { return a*b + b*c + c*a; }
const int MAXN = 100005;
struct CHT {
vector<pll> V;
void push(const pll &p) {
for(; 1 < sz(V) && ccw(befv(V), V.back(), p) >= 0; V.pop_back());
V.eb(p);
}
ll f(int i, ll X) { return V[i].first*X + V[i].second; }
ll get(ll X) {
if(V.empty()) return -INFLL;
ll ret = -INFLL;
int s = 0, e = sz(V)-1; for(int m; s < e;) {
m = (s+e) >> 1;
ll l = f(m, X), r = f(m+1, X);
if(l <= r) {
if(ret < r) ret = r;
s = m+1;
} else {
if(ret < l) ret = l;
e = m-1;
}
}
return max(ret, f(s, X));
}
} cht[MAXN];
int HI[MAXN], HR[MAXN], Hn;
vector<int> G[MAXN];
int cnt[MAXN], prt[MAXN];
ll L[MAXN], dp[MAXN];
int D[MAXN], E[MAXN];
int A[MAXN], B[MAXN], C[MAXN];
int N;
ll cal(int i, ll X) {
ll ret = -INFLL;
for(int l; i;) {
l = HI[i];
ll t = cht[l].get(X);
if(ret < t) ret = t;
i = prt[HR[l]];
}
return ret;
}
void dfs(int i) {
if(1 < i) dp[i] = -cal(i, E[i]) + D[i] + L[i]*E[i];
cht[HI[i]].push({L[i], -dp[i]});
int ni = -1, nc = -1;
for(int e : G[i]) {
int v = B[e];
if(cnt[v] <= nc) continue;
nc = cnt[v]; ni = v;
}
if(ni < 0) return;
for(int e : G[i]) {
int v = B[e];
if(v == ni) continue;
Hn++;
HI[v] = Hn; HR[Hn] = v;
dfs(v);
}
HI[ni] = HI[i];
dfs(ni);
}
void dfsinit(int i) {
cnt[i] = 1;
for(int e : G[i]) {
int v = A[e]^B[e]^i;
prt[v] = i;
L[v] = L[i] + C[e];
G[v].erase(find(allv(G[v]), e));
dfsinit(v);
cnt[i] += cnt[v];
}
}
int main() {
ios::sync_with_stdio(false);
cin >> N;
for(int i = 1; i < N; i++) {
cin >> A[i] >> B[i] >> C[i];
G[A[i]].eb(i);
G[B[i]].eb(i);
}
for(int i = 2; i <= N; i++) cin >> D[i] >> E[i];
dfsinit(1);
for(int i = 1; i < N; i++) if(prt[A[i]] == B[i]) swap(A[i], B[i]);
Hn = HI[1] = HR[1] = 1; dfs(1);
for(int i = 2; i <= N; i++) printf("%lld ", dp[i]);
puts("");
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
9 ms |
5496 KB |
Output is correct |
3 |
Correct |
64 ms |
12920 KB |
Output is correct |
4 |
Correct |
100 ms |
16680 KB |
Output is correct |
5 |
Correct |
135 ms |
19676 KB |
Output is correct |
6 |
Correct |
167 ms |
23160 KB |
Output is correct |
7 |
Correct |
89 ms |
13944 KB |
Output is correct |
8 |
Correct |
176 ms |
20044 KB |
Output is correct |
9 |
Correct |
166 ms |
22264 KB |
Output is correct |
10 |
Correct |
139 ms |
21232 KB |
Output is correct |