// https://oj.uz/problem/view/CEOI09_harbingers
#include <bits/stdc++.h>
using namespace std;
template <class C> constexpr int sz(const C &c) { return int(c.size()); }
constexpr const char nl = '\n', sp = ' '; using uint = unsigned int;
using ll = long long; using ull = unsigned long long; using ld = long double;
#if __SIZEOF_INT128__
using i128 = __int128_t; using ui128 = __uint128_t;
#endif
const bool FIRST = true, LAST = false;
template <const bool ISFIRST, class T, class F> T bsearch(T lo, T hi, F f) {
static_assert(is_integral<T>::value, "T must be integral");
hi--; while (lo <= hi) {
T mid = lo + (hi - lo) / 2;
if (f(mid) == ISFIRST) hi = mid - 1;
else lo = mid + 1;
}
return ISFIRST ? lo : hi;
}
template <class T, class Cmp = less<T>> struct ConvexHullTrickUndo {
struct Line {
T m, b; Line(T m = T(), T b = T()) : m(m), b(b) {}
T eval(T x) const { return m * x + b; }
};
vector<pair<int, Line>> history; vector<Line> L; Cmp cmp; int back;
ConvexHullTrickUndo(Cmp cmp = Cmp()) : cmp(cmp), back(0) {}
int size() const { return back; }
void addLine(T m, T b) {
int i = back; if (i >= 1)
i = bsearch<LAST>(1, i + 1, [&] (int j) {
return cmp(m, L[j - 1].m) || cmp(L[j - 1].m, m) || cmp(b, L[j - 1].b);
});
if (i >= 2)
i = bsearch<LAST>(2, i + 1, [&] (int j) {
T c1 = (L[j - 1].m - m) * (L[j - 2].b - b);
T c2 = (L[j - 1].b - b) * (L[j - 2].m - m);
return c1 > c2;
});
if (i == int(L.size())) L.emplace_back();
history.emplace_back(back, L[i]); L[i] = Line(m, b); back = i + 1;
}
void undo() { tie(back, L[back - 1]) = history.back(); history.pop_back(); }
T getMax(T x) const {
return L[bsearch<FIRST>(0, back - 1, [&] (int i) {
return cmp(L[i + 1].eval(x), L[i].eval(x));
})].eval(x);
}
void reserve(int N) { L.reserve(N); history.reserve(N); }
};
template <class T> struct StaticWeightedGraph {
vector<int> ST, TO, A, B; vector<T> C, WEIGHT;
StaticWeightedGraph(int V) : ST(V + 1, 0) {}
void reserveDiEdges(int maxEdges) {
TO.reserve(maxEdges); A.reserve(maxEdges); B.reserve(maxEdges);
}
void addDiEdge(int from, int to, T weight) {
ST[from]++; A.push_back(from); B.push_back(to); C.push_back(weight);
}
void addBiEdge(int v, int w, T weight) {
addDiEdge(v, w, weight); addDiEdge(w, v, weight);
}
void build() {
partial_sum(ST.begin(), ST.end(), ST.begin()); TO = B; WEIGHT = C;
for (int e = 0; e < int(A.size()); e++) {
TO[--ST[A[e]]] = B[e]; WEIGHT[ST[A[e]]] = C[e];
}
}
struct Iterator {
const StaticWeightedGraph &G; int i;
Iterator(const StaticWeightedGraph &G, int i) : G(G), i(i) {}
Iterator &operator ++ () { i++; return *this; }
pair<int, T> operator * () const {
return make_pair(G.TO[i], G.WEIGHT[i]);
}
bool operator != (const Iterator &it) const { return i != it.i; }
};
struct Adj {
const StaticWeightedGraph &G; int v;
Adj(const StaticWeightedGraph &G, int v) : G(G), v(v) {}
const Iterator begin() const { return Iterator(G, G.ST[v]); }
const Iterator end() const { return Iterator(G, G.ST[v + 1]); }
};
const Adj operator [] (int v) const { return Adj(*this, v); }
int size() const { return int(ST.size()) - 1; }
};
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// freopen("err.txt", "w", stderr);
ios::sync_with_stdio(0); cin.tie(0);
int N;
cin >> N;
StaticWeightedGraph<ll> G(N);
for (int i = 0; i < N - 1; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
G.addBiEdge(--a, --b, c);
}
G.build();
vector<ll> S(N, 0), V(N, 0), ans(N, 0);
for (int i = 1; i < N; i++) cin >> S[i] >> V[i];
ConvexHullTrickUndo<i128, greater<i128>> cht;
cht.reserve(N);
function<void(int, int, ll)> dfs = [&] (int v, int prev, ll d) {
if (v > 0) ans[v] = S[v] + d * V[v] + cht.getMax(V[v]);
cht.addLine(-d, ans[v]);
for (auto &&[w, weight] : G[v]) if (w != prev) dfs(w, v, d + weight);
cht.undo();
};
dfs(0, -1, 0);
for (int i = 1; i < N; i++) {
if (i > 1) cout << sp;
cout << ans[i];
}
cout << nl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
49 ms |
13080 KB |
Output is correct |
| 4 |
Correct |
73 ms |
19796 KB |
Output is correct |
| 5 |
Correct |
82 ms |
25132 KB |
Output is correct |
| 6 |
Correct |
111 ms |
31264 KB |
Output is correct |
| 7 |
Correct |
62 ms |
12644 KB |
Output is correct |
| 8 |
Correct |
117 ms |
19880 KB |
Output is correct |
| 9 |
Correct |
123 ms |
24372 KB |
Output is correct |
| 10 |
Correct |
114 ms |
22464 KB |
Output is correct |
