#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<tuple<int, int, Line>> history; vector<Line> L; int back;
ConvexHullTrickUndo() : back(0) {}
int size() const { return back; }
void addLine(T m, T b) {
int i = back; if (i >= 1) {
i = bsearch<FIRST>(1, i, [&] (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<FIRST>(2, i, [&] (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, i, L[i]); L[i] = Line(m, b); back = i + 1;
}
void undo() {
int i; Line l; tie(back, i, l) = history.back(); history.pop_back();
L[i] = l;
}
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); }
};
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;
function<void(int, int, ll)> dfs = [&] (int v, int prev, ll d) {
if (cht.size() > 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 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
1176 KB |
Output isn't correct |
| 3 |
Incorrect |
51 ms |
13096 KB |
Output isn't correct |
| 4 |
Incorrect |
70 ms |
18988 KB |
Output isn't correct |
| 5 |
Incorrect |
91 ms |
25736 KB |
Output isn't correct |
| 6 |
Incorrect |
103 ms |
31392 KB |
Output isn't correct |
| 7 |
Incorrect |
67 ms |
13864 KB |
Output isn't correct |
| 8 |
Incorrect |
137 ms |
19488 KB |
Output isn't correct |
| 9 |
Correct |
132 ms |
23676 KB |
Output is correct |
| 10 |
Incorrect |
131 ms |
23348 KB |
Output isn't correct |
