Felix's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub fffelix-huang/CP-stuff

:heavy_check_mark: test/tree/hld/aoj-grl-Range-Query-on-a-Tree-II.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_E"

#include <iostream>

#include <vector>

#include <algorithm>

#include "../../../library/tree/hld.hpp"

#include "../../../library/data-structure/lazy-segtree.hpp"

using namespace std;
using namespace felix;

struct S {
	long long sum = 0;
	int sz = 0;

	S() {}
	S(long long a, int b) : sum(a), sz(b) {}
};

S e() { return S(); }
S op(S a, S b) { return S(a.sum + b.sum, a.sz + b.sz); }

using F = int;

F id() { return 0; }

S mapping(F f, S s) {
	s.sum += 1LL * f * s.sz;
	return s;
}

F composition(F a, F b) { return a + b; }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	HLD hld(n);
	for(int i = 0; i < n; i++) {
		int m;
		cin >> m;
		for(int j = 0; j < m; j++) {
			int x;
			cin >> x;
			hld.add_edge(i, x);
		}
	}
	hld.build(0);
	lazy_segtree<S, e, op, F, id, mapping, composition> seg(vector<S>(n, S(0, 1)));
	int q;
	cin >> q;
	while(q--) {
		int type, u;
		cin >> type >> u;
		if(type == 0) {
			int w;
			cin >> w;
			for(auto [x, y] : hld.get_path(0, u, false)) {
				if(hld.id[x] > hld.id[y]) {
					swap(x, y);
				}
				seg.apply(hld.id[x], hld.id[y] + 1, F{w});
			}
		} else {
			S ans = e();
			for(auto [x, y] : hld.get_path(0, u, false)) {
				if(hld.id[x] > hld.id[y]) {
					swap(x, y);
				}
				ans = op(ans, seg.prod(hld.id[x], hld.id[y] + 1));
			}
			cout << ans.sum << "\n";
		}
	}
	return 0;
}
#line 1 "test/tree/hld/aoj-grl-Range-Query-on-a-Tree-II.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_E"

#include <iostream>

#include <vector>

#include <algorithm>

#line 3 "library/tree/hld.hpp"
#include <array>

#include <cassert>

#line 6 "library/tree/hld.hpp"
#include <cmath>

#line 4 "library/data-structure/sparse-table.hpp"

namespace felix {

template<class S, S (*op)(S, S)>
struct sparse_table {
public:
	sparse_table() {}
	explicit sparse_table(const std::vector<S>& a) {
		n = (int) a.size();
		int max_log = std::__lg(n) + 1;
		mat.resize(max_log);
		mat[0] = a;
		for(int j = 1; j < max_log; ++j) {
			mat[j].resize(n - (1 << j) + 1);
			for(int i = 0; i <= n - (1 << j); ++i) {
				mat[j][i] = op(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	S prod(int from, int to) const {
		assert(0 <= from && from <= to && to <= n - 1);
		int lg = std::__lg(to - from + 1);
		return op(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
	}

private:
	int n;
	std::vector<std::vector<S>> mat;
};

} // namespace felix
#line 8 "library/tree/hld.hpp"

namespace felix {

struct HLD {
private:
	static constexpr std::pair<int, int> __lca_op(std::pair<int, int> a, std::pair<int, int> b) {
		return std::min(a, b);
	}

public:
	int n;
	std::vector<std::vector<int>> g;
	std::vector<int> subtree_size;
	std::vector<int> parent;
	std::vector<int> depth;
	std::vector<int> top;
	std::vector<int> tour;
	std::vector<int> first_occurrence;
	std::vector<int> id;
	std::vector<std::pair<int, int>> euler_tour;
	sparse_table<std::pair<int, int>, __lca_op> st;

	HLD() : n(0) {}
	explicit HLD(int _n) : n(_n), g(_n), subtree_size(_n), parent(_n), depth(_n), top(_n), first_occurrence(_n), id(_n) {
		tour.reserve(n);
		euler_tour.reserve(2 * n - 1);
	}

	void add_edge(int u, int v) {
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		g[u].push_back(v);
		g[v].push_back(u);
	}

	void build(int root = 0) {
		assert(0 <= root && root < n);
		parent[root] = -1;
		top[root] = root;
		dfs_sz(root);
		dfs_link(root);
		st = std::move(sparse_table<std::pair<int, int>, __lca_op>(euler_tour));
	}

	int get_lca(int u, int v) {
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		int L = first_occurrence[u];
		int R = first_occurrence[v];
		if(L > R) {
			std::swap(L, R);
		}
		return st.prod(L, R).second;
	}

	bool is_ancestor(int u, int v) {
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		return id[u] <= id[v] && id[v] < id[u] + subtree_size[u];
	}

	bool on_path(int a, int x, int b) {
		return (is_ancestor(x, a) || is_ancestor(x, b)) && is_ancestor(get_lca(a, b), x);
	}

	int get_distance(int u, int v) {
		return depth[u] + depth[v] - 2 * depth[(get_lca(u, v))];
	}

	std::pair<int, std::array<int, 2>> get_diameter() const {
		std::pair<int, int> u_max = {-1, -1};
		std::pair<int, int> ux_max = {-1, -1};
		std::pair<int, std::array<int, 2>> uxv_max = {-1, std::array<int, 2>{-1, -1}};
		for(auto [d, u] : euler_tour) {
			u_max = std::max(u_max, std::make_pair(d, u));
			ux_max = std::max(ux_max, std::make_pair(u_max.first - 2 * d, u_max.second));
			uxv_max = std::max(uxv_max, std::make_pair(ux_max.first + d, std::array<int, 2>{ux_max.second, u}));
		}
		return uxv_max;
	}

	int get_kth_ancestor(int u, int k) {
		assert(0 <= u && u < n);
		if(depth[u] < k) {
			return -1;
		}
		int d = depth[u] - k;
		while(depth[top[u]] > d) {
			u = parent[top[u]];
		}
		return tour[id[u] + d - depth[u]];
	}

	int get_kth_node_on_path(int a, int b, int k) {
		int z = get_lca(a, b);
		int fi = depth[a] - depth[z];
		int se = depth[b] - depth[z];
		if(k < 0 || k > fi + se) {
			return -1;
		}
		if(k < fi) {
			return get_kth_ancestor(a, k);
		} else {
			return get_kth_ancestor(b, fi + se - k);
		}
	}

	std::vector<std::pair<int, int>> get_path(int u, int v, bool include_lca) {
		if(u == v && !include_lca) {
			return {};
		}
		std::vector<std::pair<int, int>> lhs, rhs;
		while(top[u] != top[v]) {
			if(depth[top[u]] > depth[top[v]]) {
				lhs.emplace_back(u, top[u]);
				u = parent[top[u]];
			} else {
				rhs.emplace_back(top[v], v);
				v = parent[top[v]];
			}
		}
		if(u != v || include_lca) {
			if(include_lca) {
				lhs.emplace_back(u, v);
			} else {
				int d = std::abs(depth[u] - depth[v]);
				if(depth[u] < depth[v]) {
					rhs.emplace_back(tour[id[v] - d + 1], v);
				} else {
					lhs.emplace_back(u, tour[id[u] - d + 1]);
				}
			}
		}
		std::reverse(rhs.begin(), rhs.end());
		lhs.insert(lhs.end(), rhs.begin(), rhs.end());
		return lhs;
	}

private:
	void dfs_sz(int u) {
		if(parent[u] != -1) {
			g[u].erase(std::find(g[u].begin(), g[u].end(), parent[u]));
		}
		subtree_size[u] = 1;
		for(auto& v : g[u]) {
			parent[v] = u;
			depth[v] = depth[u] + 1;
			dfs_sz(v);
			subtree_size[u] += subtree_size[v];
			if(subtree_size[v] > subtree_size[g[u][0]]) {
				std::swap(v, g[u][0]);
			}
		}
	}

	void dfs_link(int u) {
		first_occurrence[u] = (int) euler_tour.size();
		id[u] = (int) tour.size();
		euler_tour.emplace_back(depth[u], u);
		tour.push_back(u);
		for(auto v : g[u]) {
			top[v] = (v == g[u][0] ? top[u] : v);
			dfs_link(v);
			euler_tour.emplace_back(depth[u], u);
		}
	}
};

} // namespace felix

#line 4 "library/data-structure/lazy-segtree.hpp"
#include <functional>
#line 6 "library/data-structure/segtree.hpp"

namespace felix {

template<class S, S (*e)(), S (*op)(S, S)>
struct segtree {
public:
    segtree() {}
    explicit segtree(int _n) : segtree(std::vector<S>(_n, e())) {}
    explicit segtree(const std::vector<S>& a): n(a.size()) {
        log = std::__lg(2 * n - 1);
        size = 1 << log;
        d.resize(size * 2, e());
        for(int i = 0; i < n; ++i) {
            d[size + i] = a[i];
        }
        for(int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    
    void set(int p, S val) {
        assert(0 <= p && p < n);
        p += size;
        d[p] = val;
        for(int i = 1; i <= log; ++i) {
            update(p >> i);
        }
    }

    S get(int p) const {
        assert(0 <= p && p < n);
        return d[p + size];
    }

    S operator[](int p) const { return get(p); }
    
    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        S sml = e(), smr = e();
        for(l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if(l & 1) {
                sml = op(sml, d[l++]);
            }
            if(r & 1) {
                smr = op(d[--r], smr);
            }
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template<bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }

    template<class F> int max_right(int l, F f) {
        assert(0 <= l && l <= n);
        assert(f(e()));
        if(l == n) {
            return n;
        }
        l += size;
        S sm = e();
        do {
            while(~l & 1) {
                l >>= 1;
            }
            if(!f(op(sm, d[l]))) {
                while(l < size) {
                    push(l);
                    l <<= 1;
                    if(f(op(sm, d[l]))) {
                        sm = op(sm, d[l++]);
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l++]);
        } while((l & -l) != l);
        return n;
    }

    template<bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }

    template<class F> int min_left(int r, F f) {
        assert(0 <= r && r <= n);
        assert(f(e()));
        if(r == 0) {
            return 0;
        }
        r += size;
        S sm = e();
        do {
            r--;
            while(r > 1 && (r & 1)) {
                r >>= 1;
            }
            if(!f(op(d[r], sm))) {
                while(r < size) {
                    push(r);
                    r = 2 * r + 1;
                    if(f(op(d[r], sm))) {
                        sm = op(d[r--], sm);
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while((r & -r) != r);
        return 0;
    }
    
protected:
    int n, size, log;
    std::vector<S> d;

    void update(int v) {
        d[v] = op(d[2 * v], d[2 * v + 1]);
    }

    virtual void push(int p) {}
};

} // namespace felix
#line 7 "library/data-structure/lazy-segtree.hpp"

namespace felix {

template<class S,
         S (*e)(),
         S (*op)(S, S),
         class F,
         F (*id)(),
         S (*mapping)(F, S),
         F (*composition)(F, F)>
struct lazy_segtree : public segtree<S, e, op> {
	using base = segtree<S, e, op>;

public:
	lazy_segtree() {}
	explicit lazy_segtree(int _n) : lazy_segtree(std::vector<S>(_n, e())) {}
	explicit lazy_segtree(const std::vector<S>& v) : base(v), lz(size, id()) {}

	void set(int p, S x) {
		push_down(p);
		base::set(p, x);
	}

	S get(int p) {
		push_down(p);
		return base::get(p);
	}

	S operator[](int p) { return get(p); }

	S prod(int l, int r) {
		if(l == r) {
			return e();
		}
		push_down(l, r);
		return base::prod(l, r);
	}

	void apply(int p, F f) {
		assert(0 <= p && p < n);
		push_down(p);
		base::set(p, mapping(f, d[p]));
	}

	void apply(int l, int r, F f) {
		assert(0 <= l && l <= r && r <= n);
		if(l == r) {
			return;
		}
		push_down(l, r);
		l += size, r += size;
		{
			int l2 = l, r2 = r;
			while(l < r) {
				if(l & 1) {
					all_apply(l++, f);
				}
				if(r & 1) {
					all_apply(--r, f);
				}
				l >>= 1, r >>= 1;
			}
			l = l2, r = r2;
		}
		for(int i = 1; i <= log; i++) {
			if(((l >> i) << i) != l) {
				update(l >> i);
			}
			if(((r >> i) << i) != r) {
				update((r - 1) >> i);
			}
		}
	}

	template<bool (*g)(S)> int max_right(int l) {
		return max_right(l, [](S x) { return g(x); });
	}

	template<class G> int max_right(int l, G g) {
		assert(0 <= l && l <= n);
		assert(g(e()));
		if(l == n) {
			return n;
		}
		push_down(l);
		return base::max_right(l, g);
	}

	template<bool (*g)(S)> int min_left(int r) {
		return min_left(r, [](S x) { return g(x); });
	}

	template<class G> int min_left(int r, G g) {
		assert(0 <= r && r <= n);
		assert(g(e()));
		if(r == 0) {
			return 0;
		}
		push_down(r - 1);
		return base::min_left(r, g);
	}

protected:
	using base::n, base::log, base::size, base::d;
	using base::update;

	std::vector<F> lz;

	virtual void all_apply(int k, F f) {
		d[k] = mapping(f, d[k]);
		if(k < size) {
			lz[k] = composition(f, lz[k]);
		}
	}

	void push(int k) override {
		all_apply(2 * k, lz[k]);
		all_apply(2 * k + 1, lz[k]);
		lz[k] = id();
	}

	void push_down(int p) {
		p += size;
		for(int i = log; i >= 1; i--) {
			push(p >> i);
		}
	}

	void push_down(int l, int r) {
		l += size, r += size;
		for(int i = log; i >= 1; i--) {
			if(((l >> i) << i) != l) {
				push(l >> i);
			}
			if(((r >> i) << i) != r) {
				push((r - 1) >> i);
			}
		}
	}
};

} // namespace felix
#line 8 "test/tree/hld/aoj-grl-Range-Query-on-a-Tree-II.test.cpp"
using namespace std;
using namespace felix;

struct S {
	long long sum = 0;
	int sz = 0;

	S() {}
	S(long long a, int b) : sum(a), sz(b) {}
};

S e() { return S(); }
S op(S a, S b) { return S(a.sum + b.sum, a.sz + b.sz); }

using F = int;

F id() { return 0; }

S mapping(F f, S s) {
	s.sum += 1LL * f * s.sz;
	return s;
}

F composition(F a, F b) { return a + b; }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	HLD hld(n);
	for(int i = 0; i < n; i++) {
		int m;
		cin >> m;
		for(int j = 0; j < m; j++) {
			int x;
			cin >> x;
			hld.add_edge(i, x);
		}
	}
	hld.build(0);
	lazy_segtree<S, e, op, F, id, mapping, composition> seg(vector<S>(n, S(0, 1)));
	int q;
	cin >> q;
	while(q--) {
		int type, u;
		cin >> type >> u;
		if(type == 0) {
			int w;
			cin >> w;
			for(auto [x, y] : hld.get_path(0, u, false)) {
				if(hld.id[x] > hld.id[y]) {
					swap(x, y);
				}
				seg.apply(hld.id[x], hld.id[y] + 1, F{w});
			}
		} else {
			S ans = e();
			for(auto [x, y] : hld.get_path(0, u, false)) {
				if(hld.id[x] > hld.id[y]) {
					swap(x, y);
				}
				ans = op(ans, seg.prod(hld.id[x], hld.id[y] + 1));
			}
			cout << ans.sum << "\n";
		}
	}
	return 0;
}
Back to top page