#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INFLL = (1LL<<62);
// ---------- Li Chao on a fixed set of x-coordinates (segment-style) ----------
// Lines: y = m*x + b
struct Line {
ll m, b;
Line(ll _m = 0, ll _b = INFLL) : m(_m), b(_b) {}
inline ll eval_ll(ll x) const {
__int128 v = ( __int128 )m * x + b;
if (v > INFLL) return INFLL;
if (v < -INFLL) return -INFLL;
return (ll)v;
}
};
// segment tree holds a line on each node, node range corresponds to discrete x indices [L..R]
// xs[] holds the real x coordinate for each index.
struct LiChaoSeg {
int M; // number of distinct x values
vector<Line> seg; // size 4*M
vector<ll> xs; // sorted distinct x coordinates
// change record for rollback: node index + previous line
struct Change { int node; Line old; };
vector<Change> changes;
vector<int> checkpoints;
LiChaoSeg() : M(0) {}
void init_from_xs(vector<ll> &coords) {
xs = coords;
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
M = (int)xs.size();
seg.assign(4 * max(1, M), Line());
changes.clear();
checkpoints.clear();
}
// insert tracked: push checkpoint, then call insert_impl
void insert_tracked(Line newline) {
checkpoints.push_back((int)changes.size());
if (M > 0) insert_impl(1, 0, M - 1, newline);
}
void rollback_last_insert() {
if (checkpoints.empty()) return;
int target = checkpoints.back();
checkpoints.pop_back();
while ((int)changes.size() > target) {
Change ch = changes.back();
changes.pop_back();
seg[ch.node] = ch.old;
}
}
// record change of seg[node]
inline void record_node(int node) {
changes.push_back({node, seg[node]});
}
// insertion on indices interval [l,r]
void insert_impl(int node, int l, int r, Line newline) {
int mid = (l + r) >> 1;
ll xl = xs[l], xm = xs[mid], xr = xs[r];
Line cur = seg[node];
// compare at mid value
bool leftBetter = newline.eval_ll(xl) < cur.eval_ll(xl);
bool midBetter = newline.eval_ll(xm) < cur.eval_ll(xm);
if (midBetter) {
// overwrite node's line (record old)
record_node(node);
swap(seg[node], newline);
// now newline holds old seg[node]
cur = seg[node]; // updated
}
if (l == r) return;
if (leftBetter != midBetter) {
// affects left child
insert_impl(node<<1, l, mid, newline);
} else {
// affects right child
insert_impl(node<<1|1, mid+1, r, newline);
}
}
// query value at actual x (which must exist in xs)
ll query_at_x(ll x) const {
if (M == 0) return INFLL;
int idx = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
// assume x is present in xs
return query_impl(1, 0, M - 1, idx, x);
}
ll query_impl(int node, int l, int r, int idx, ll x) const {
ll res = seg[node].eval_ll(x);
if (l == r) return res;
int mid = (l + r) >> 1;
if (idx <= mid) return min(res, query_impl(node<<1, l, mid, idx, x));
else return min(res, query_impl(node<<1|1, mid+1, r, idx, x));
}
};
// ---------------- Problem-specific code (Harbingers COI 2009) ----------------
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#if defined(__GNUC__)
// optional: increase recursion depth if needed
#endif
int N;
if (!(cin >> N)) return 0;
vector<vector<pair<int,int>>> adj(N);
for (int i = 0; i < N-1; ++i) {
int u,v,d; cin >> u >> v >> d;
--u; --v;
adj[u].push_back({v,d});
adj[v].push_back({u,d});
}
// S and V for nodes 2..N (input gives N-1 pairs)
vector<ll> S(N, 0), V(N, 0);
for (int i = 1; i < N; ++i) {
cin >> S[i] >> V[i];
}
// compute dist from root (node 0)
vector<ll> dist(N, 0);
// we will also need parent order for DFS
vector<int> parent(N, -1), order; order.reserve(N);
// iterative stack to avoid recursion limit when computing distances
{
order.push_back(0);
parent[0] = -2; // mark root visited
for (size_t i = 0; i < order.size(); ++i) {
int u = order[i];
for (auto [v, w] : adj[u]) if (parent[v] == -1) {
parent[v] = u;
dist[v] = dist[u] + w;
order.push_back(v);
}
}
}
// prepare xs = distinct V[i] (only nodes 1..N-1 have V)
vector<ll> xs;
xs.reserve(N);
for (int i = 1; i < N; ++i) xs.push_back(V[i]);
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
LiChaoSeg lich;
lich.init_from_xs(xs);
// We'll perform a DFS from root and maintain Li Chao with rollback:
// - at entering node u: if u==0 (root) dp[0]=0 and we insert line for root: slope = -dist[0]=0, intercept = dp[0]=0
// - for other u: dp[u] = query(V[u]) + dist[u]*V[u] + S[u]; then insert line with slope = -dist[u], intercept = dp[u]
// After processing children, rollback last insert.
vector<ll> dp(N, 0);
// iterative DFS with manual stack to manage rollback points and visiting order (enter/exit)
struct Frame { int u; int p; int it; bool entered; };
vector<Frame> stack;
stack.push_back({0, -1, 0, false});
while (!stack.empty()) {
Frame f = stack.back(); stack.pop_back();
int u = f.u, p = f.p;
if (!f.entered) {
// ENTRY
// compute dp
if (u == 0) {
dp[u] = 0;
} else {
ll best = lich.query_at_x(V[u]);
// if lich gave INF (tree empty), best will be INF -> dp huge; but root line exists from root insertion
dp[u] = best;
if (dp[u] >= INFLL/4) dp[u] = INFLL; // safe
else {
dp[u] = dp[u] + dist[u] * V[u] + S[u];
}
}
// push EXIT frame
stack.push_back({u, p, 0, true});
// insert this node's line into Li Chao
// line: y(x) = (-dist[u])*x + dp[u]
Line L(-dist[u], dp[u]);
lich.insert_tracked(L);
// push children (enter frames) onto stack
for (auto &ed : adj[u]) {
int v = ed.first;
if (v == p) continue;
stack.push_back({v, u, 0, false});
}
} else {
// EXIT: rollback the insertion we did on ENTRY for this node
lich.rollback_last_insert();
}
}
// print dp[1..N-1]
for (int i = 1; i < N; ++i) {
cout << dp[i] << (i+1 < N ? ' ' : '\n');
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
