#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/**
* A Persistant Li Chao Impelementation
* Useful for Convex Hull Trick on Trees
* Complexity: O(log C)
* Verified: https://judge.yosupo.jp/problem/line_add_get_min
*/
struct PersistantLiChao {
struct Line {
int64_t m, b;
Line(int64_t _m = 0, int64_t _b = numeric_limits<int64_t>::min()) : m(_m), b(_b) {}
int64_t operator()(int64_t x) { return m * x + b; }
friend ostream& operator<<(ostream &os, const Line &l) { return os << l.m << "x + " << l.b; }
~Line() {}
};
struct Node {
Line line;
size_t left = -1, right = -1;
Node(size_t _left, size_t _right) : left(_left), right(_right) {}
Node(Line _line = Line(), size_t _left = -1, size_t _right = -1) : line(_line), left(_left), right(_right) {}
};
vector<int> roots;
vector<Node> nodes;
private:
int64_t x_min, x_max;
int node(Line line, int left = -1, int right = -1) {
nodes.emplace_back(line, left, right);
return nodes.size() - 1;
}
int add(int root, Line line, int64_t l, int64_t r) {
if (root == -1)
return node(line);
int64_t root_l = nodes[root].line(l), root_r = nodes[root].line(r);
int64_t line_l = line(l), line_r = line(r);
if (root_l >= line_l && root_r >= line_r)
return root;
if (root_l <= line_l && root_r <= line_r)
return node(line, nodes[root].left, nodes[root].right);
int64_t m = (l + r) / 2;
int64_t root_m = nodes[root].line(m), line_m = line(m);
if (root_m > line_m) {
if (line_l >= root_l)
return node(nodes[root].line, add(nodes[root].left, line, l, m), nodes[root].right);
else
return node(nodes[root].line, nodes[root].left, add(nodes[root].right, line, m + 1, r));
} else {
if (root_l >= line_l)
return node(line, add(nodes[root].left, nodes[root].line, l, m), nodes[root].right);
else
return node(line, nodes[root].left, add(nodes[root].right, nodes[root].line, m + 1, r));
}
}
int64_t query(int root, int64_t x, int64_t l, int64_t r) {
if (root == -1)
return numeric_limits<int64_t>::min();
if (l == r)
return nodes[root].line(x);
int64_t m = (l + r) / 2;
if (x <= m)
return max(nodes[root].line(x), query(nodes[root].left, x, l, m));
else
return max(nodes[root].line(x), query(nodes[root].right, x, m + 1, r));
}
public:
PersistantLiChao(int N, int64_t _x_min, int64_t _x_max) : x_min(_x_min), x_max(_x_max) {
roots.resize(N, -1);
}
void add(int r, const int64_t &m, const int64_t &b) {
Line line(m, b);
roots[r] = (add(roots[r], line, x_min, x_max));
}
int64_t query(int r, int64_t x) {
return query(roots[r], x, x_min, x_max);
}
int copy(int r) {
roots.emplace_back(roots[r]);
return roots.size() - 1;
}
int copy(int r1, int r2) {
roots[r2] = roots[r1];
return r2;
}
~PersistantLiChao() {}
};
ll N, S[100005], V[100005], dp[100005];
vector<pll> T[100005];
PersistantLiChao plc(100005, 0, 1e9);
void dfs(int u, int p, ll pre) {
if (u == 1) {
dp[u] = 0;
plc.add(u, 0, 0);
}
else {
dp[u] = -plc.query(u, V[u]) + S[u] + pre * V[u];
plc.add(u, pre, -dp[u]);
}
for (auto [v, w] : T[u])
if (v != p) {
plc.copy(u, v);
dfs(v, u, pre + w);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
plc.nodes.reserve(100005);
cin >> N;
for (int i = 1; i < N; i++) {
int u, v, w;
cin >> u >> v >> w;
T[u].emplace_back(v, w);
T[v].emplace_back(u, w);
}
for (int i = 2; i <= N; i++)
cin >> S[i] >> V[i];
dfs(1, 0, 0);
for (int i = 2; i <= N; i++)
cout << dp[i] << ' ';
cout << '\n';
}
Compilation message
harbingers.cpp:106:8: error: 'pll' was not declared in this scope; did you mean 'll'?
106 | vector<pll> T[100005];
| ^~~
| ll
harbingers.cpp:106:11: error: template argument 1 is invalid
106 | vector<pll> T[100005];
| ^
harbingers.cpp:106:11: error: template argument 2 is invalid
harbingers.cpp: In function 'void dfs(int, int, ll)':
harbingers.cpp:118:27: error: 'begin' was not declared in this scope
118 | for (auto [v, w] : T[u])
| ^
harbingers.cpp:118:27: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from harbingers.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: 'std::begin'
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from harbingers.cpp:1:
/usr/include/c++/10/bits/fs_dir.h:549:3: note: 'std::filesystem::__cxx11::begin'
549 | begin(recursive_directory_iterator __iter) noexcept
| ^~~~~
harbingers.cpp:118:27: error: 'end' was not declared in this scope
118 | for (auto [v, w] : T[u])
| ^
harbingers.cpp:118:27: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from harbingers.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: 'std::end'
1244 | end(const valarray<_Tp>& __va)
| ^~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from harbingers.cpp:1:
/usr/include/c++/10/bits/fs_dir.h:554:3: note: 'std::filesystem::__cxx11::end'
554 | end(recursive_directory_iterator) noexcept
| ^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:133:14: error: request for member 'emplace_back' in 'T[u]', which is of non-class type 'int'
133 | T[u].emplace_back(v, w);
| ^~~~~~~~~~~~
harbingers.cpp:134:14: error: request for member 'emplace_back' in 'T[v]', which is of non-class type 'int'
134 | T[v].emplace_back(u, w);
| ^~~~~~~~~~~~
