Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct Hld {
- struct Segtree {
- int n;
- vector<int> t;
- void build(int v, int tl, int tr, vector<int>& a) {
- if (tl == tr) t[v] = a[tl];
- else {
- int tm = (tl + tr) / 2;
- build(v * 2, tl, tm, a); build(v * 2 + 1, tm + 1, tr, a);
- t[v] = max(t[v * 2], t[v * 2 + 1]);
- }
- }
- Segtree() {}
- void init(vector<int>& a) {
- n = (int)a.size();
- t.resize(4 * n, -inf);
- build(1, 0, n - 1, a);
- }
- void update(int v, int tl, int tr, int pos, int now) {
- if (tl == tr) t[v] = now;
- else {
- int tm = (tl + tr) / 2;
- if (pos <= tm) update(v * 2, tl, tm, pos, now);
- else update(v * 2 + 1, tm + 1, tr, pos, now);
- t[v] = max(t[v * 2], t[v * 2 + 1]);
- }
- }
- int get_mx(int v, int tl, int tr, int l, int r) {
- if (tr<l || tl>r) return -inf;
- if (tl >= l && tr <= r) return t[v];
- int tm = (tl + tr) / 2;
- return max(get_mx(v * 2, tl, tm, l, r), get_mx(v * 2 + 1, tm + 1, tr, l, r));
- }
- };
- vector<vector<int>> gr;
- int t, Size_n;
- vector<int> siz, tin, tout, head, euler_dfs, p, w;
- Hld() {}
- Hld(int _n) :Size_n(_n) {
- w.resize(Size_n), gr.resize(Size_n);
- }
- inline void Scan_weight() {
- for (int& i : w)cin >> i;
- }
- inline void Scan_tree() {
- for (int i = 0; i < Size_n - 1; i++) {
- int u, v;
- cin >> u >> v;
- u--, v--;
- gr[u].push_back(v);
- gr[v].push_back(u);
- }
- }
- void sizes(int v, int pr) {
- p[v] = pr, siz[v] = 1;
- gr[v].erase(find(all(gr[v]), pr));
- for (int& u : gr[v]) {
- sizes(u, v);
- siz[v] += siz[u];
- if (siz[u] > siz[gr[v][0]]) {
- swap(u, gr[v][0]);
- }
- }
- }
- void hld(int v) {
- tin[v] = t++; euler_dfs.push_back(w[v]);
- for (int& u : gr[v]) {
- if (u == gr[v][0]) head[u] = head[v];
- else head[u] = u;
- hld(u);
- }
- tout[v] = t;
- }
- Segtree Euler;
- void build() {
- gr[0].push_back(0);
- t = 0;
- siz.resize(Size_n), tin.resize(Size_n), tout.resize(Size_n), head.resize(Size_n), p.resize(Size_n);
- sizes(0, 0);
- hld(0);
- Euler.init(euler_dfs);
- }
- inline void up(int& u, int& v, int& ans, auto& ancestor) {
- while (!ancestor(head[u], v)) {
- ans = max(ans, Euler.get_mx(1, 0, Euler.n - 1, tin[head[u]], tin[u]));
- u = p[head[u]];
- }
- }
- int get_max(int u, int v) {
- auto ancestor = [&](const int& u, const int& v) {
- return tin[u] <= tin[v] && tout[u] > tin[v];
- };
- int ans = -inf;
- up(u, v, ans, ancestor);
- up(v, u, ans, ancestor);
- if (!ancestor(u, v)) swap(u, v);
- ans = max(ans, Euler.get_mx(1, 0, Euler.n - 1, tin[u], tin[v]));
- return ans;
- }
- inline void update(const int& u, const int& new_val) {
- Euler.update(1, 0, Euler.n - 1, tin[u], new_val);
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement