#include <bits/stdc++.h>
using namespace std;
//long long MOD = 1e9 + 7;
const long long MOD = 998244353;
// const long long MOD = 100000007 ;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define popCnt(x) (__builtin_popcountll(x))
#define int long long
#define ld long double
#define F first
#define S second
#define pi M_PI
#define all(x) x.begin() , x.end()
#define ll long long
#define SZ(v) (int)(v.size())
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const long long OO = LLONG_MAX / 4, N = 3e5 + 5, M = 1e5 + 5, K = 505;
// ---------- rollback-optimized LineContainer ----------
struct Line {
mutable ll k, m, p;
bool operator<(const Line &o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct RollbackLineContainer : multiset<Line, less<>> {
static const ll inf = LLONG_MAX;
bool isMn = true;
// Operation types that we may need to revert
enum OpType { OP_INSERT, OP_ERASE, OP_SETP };
struct Op {
OpType type;
Line data; // for OP_INSERT/OP_ERASE we store the full line; for OP_SETP we store old line (with old p)
};
// single pool of ops for ALL adds (avoids per-add allocations)
vector<Op> opsPool;
// stack of indices into opsPool marking where each add started
vector<size_t> addStart;
RollbackLineContainer() {
opsPool.reserve(1 << 20); // heuristic reserve to avoid reallocation (tweak as needed)
addStart.reserve(1 << 18);
}
// call if you want to pre-reserve based on expected number of adds
void reserve_history(size_t expected_adds, size_t avg_ops_per_add = 8) {
addStart.reserve(expected_adds);
opsPool.reserve(expected_adds * avg_ops_per_add);
}
// integer division matching original behavior (floor for negatives)
ll divll(ll a, ll b) {
return a / b - ((a ^ b) < 0 && a % b);
}
// helper: set p via mutable
void set_p(iterator it, ll newp) {
const_cast<ll&>(it->p) = newp;
}
// find a line with exact (k,m) using lower_bound (log n)
iterator find_same(const Line &target) {
auto it = lower_bound(target); // compares by k
for (; it != end() && it->k == target.k; ++it) {
if (it->m == target.m) return it;
}
return end();
}
// log erase: push saved copy to opsPool then erase
iterator erase_with_log(iterator it) {
opsPool.push_back({OP_ERASE, *it});
return erase(it);
}
// isect with logging (stores previous p if changed), returns same boolean as before
bool isect_log(iterator x, iterator y) {
if (y == end()) {
if (x->p != inf) opsPool.push_back({OP_SETP, *x});
set_p(x, inf);
return false;
}
if (x->k == y->k) {
ll newp = x->m > y->m ? inf : -inf;
if (x->p != newp) opsPool.push_back({OP_SETP, *x});
set_p(x, newp);
} else {
ll newp = divll(y->m - x->m, x->k - y->k);
if (x->p != newp) opsPool.push_back({OP_SETP, *x});
set_p(x, newp);
}
return x->p >= y->p;
}
// add a line, logging minimal info into the single opsPool
void add(ll k, ll m) {
size_t startIndex = opsPool.size(); // mark where this add's ops start
addStart.push_back(startIndex);
if (isMn) { k = -k; m = -m; }
auto z = insert({k, m, 0});
opsPool.push_back({OP_INSERT, *z}); // remember insertion so rollback removes it
auto y = z++;
auto x = y;
while (isect_log(y, z)) {
z = erase_with_log(z);
}
if (x != begin() && isect_log(--x, y)) {
// erase y (logged) and re-evaluate
y = erase_with_log(y);
isect_log(x, y);
}
while ((y = x) != begin()) {
--x;
if (x->p >= y->p) {
// erase y (logged) and update x's p (logged in isect_log)
auto nxt = erase_with_log(y);
isect_log(x, nxt);
} else break;
}
}
// query unchanged
ll query(ll x) {
auto l = *lower_bound(x);
return (isMn ? -1 : 1) * (l.k * x + l.m);
}
// rollback the last add (undo in reverse order)
void rollback() {
if (addStart.empty()) return;
size_t start = addStart.back();
addStart.pop_back();
// revert ops in reverse order
for (size_t idx = opsPool.size(); idx-- > start; ) {
Op &op = opsPool[idx];
if (op.type == OP_ERASE) {
// inverse of erase: re-insert the stored copy
insert(op.data);
} else if (op.type == OP_SETP) {
// inverse of set-p: find the line with same (k,m) and restore its p
auto it = find_same(op.data);
if (it != end()) set_p(it, op.data.p);
} else if (op.type == OP_INSERT) {
// inverse of insert: find the inserted line and erase it
auto it = find_same(op.data);
if (it != end()) erase(it);
}
}
// shrink opsPool back to 'start'
opsPool.resize(start);
}
// rollback last t adds (safe if t > history size)
void rollback_n(size_t t) {
while (t-- && !addStart.empty()) rollback();
}
// clear history to free memory of the opsPool
void clear_history() {
opsPool.clear();
addStart.clear();
}
};
RollbackLineContainer cht;
int n;
vector<int> v, c;
vector<vector<pair<int, int>>> adj;
vector<int> dp;
void dfs(int node , int p = -1 , int d = 0)
{
if(p == -1) dp[node] = 0;
else dp[node] = cht.query(v[node]) + v[node] * d + c[node];
cht.add(-d , dp[node]);
for(auto [child , len] : adj[node])
{
if(child == p)continue;
dfs(child , node , d + len);
}
cht.rollback();
}
signed main() {
fast;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n;
dp = v = c = vector<int>(n);
adj.resize(n);
for (int i = 0; i < n - 1; ++i) {
int u, vv, d;
cin >> u >> vv >> d;
u--;
vv--;
adj[u].emplace_back(vv, d);
adj[vv].emplace_back(u, d);
}
for (int i = 1; i < n; ++i) {
cin >> c[i] >> v[i];
}
dfs(0);
for(int i = 1 ; i < n ; i++) cout << dp[i] << " ";
cout<<'\n';
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
