#include using namespace std; template using V = vector; template using VV = V>; using ll = int64_t; template struct HeavyLightDecomposition { ll root; const Graph &graph; V subtree_size, head, parent_node_idx, decomposed_id, component_id, heavy_edge_to; HeavyLightDecomposition(const Graph &graph) : root(0), graph(graph), subtree_size(graph.size()), head(graph.size()), parent_node_idx(graph.size()), decomposed_id(graph.size()), component_id(graph.size()), heavy_edge_to(graph.size()) { } ll count_size(ll cur, ll pre) { ll ret = 1; parent_node_idx[cur] = pre; ll max_size = 0, max_size_to = -1; for(ll nxt : graph[cur]) { if(nxt == pre) continue; ll res = count_size(nxt, cur); if(max_size < res) { max_size = res; max_size_to = nxt; } ret += res; } heavy_edge_to[cur] = max_size_to; return subtree_size[cur] = ret; } ll get_decomposed_id(ll node) { return node == -1 ? -1 : decomposed_id[node]; } void build_component(ll cur, ll pre, ll &decomposed_id_counter, ll &total_hl) { decomposed_id[cur] = decomposed_id_counter++; component_id[cur] = total_hl; head[cur] = (get_decomposed_id(pre) == -1 ? cur : component_id[cur] == component_id[pre] ? head[pre] : cur); if(heavy_edge_to[cur] != -1) build_component(heavy_edge_to[cur], cur, decomposed_id_counter, total_hl); for(ll nxt : graph[cur]) { if(nxt == pre || nxt == heavy_edge_to[cur]) continue; build_component(nxt, cur, decomposed_id_counter, ++total_hl); } } void decompose() { count_size(root, -1); ll decomposed_id_counter = 0; ll total_hl = 0; build_component(root, -1, decomposed_id_counter, total_hl); } // careful : when query handle edges template T query(ll n1, ll n2, const function &calc_component, T identity, const function &merge) { T lval = identity, rval = identity; T result = identity; while(true) { if(component_id[n1] != component_id[n2]) { if(decomposed_id[n1] < decomposed_id[n2]) { T tmp = calc_component(decomposed_id[head[n2]], decomposed_id[n2] + 1); rval = merge(tmp, rval); n2 = parent_node_idx[head[n2]]; } else { T tmp = calc_component(decomposed_id[head[n1]], decomposed_id[n1] + 1); lval = merge(lval, tmp); n1 = parent_node_idx[head[n1]]; } } else { ll id1 = decomposed_id[n1]; ll id2 = decomposed_id[n2]; result = calc_component(min(id1, id2), max(id1, id2) + 1); result = merge(lval, result); result = merge(result, rval); break; } } return result; } void query(ll n1, ll n2, const function &calc_component) { ll identity = 0; auto merge = [&](ll a, ll b) { return 0; }; auto wrapper_calc = [&](ll a, ll b) { calc_component(a, b); return 0; }; query(n1, n2, wrapper_calc, identity, merge); } }; // solution for https://yukicoder.me/problems/no/399 template class LazySegmentTree{ private: ll N; T init_node; L init_lazy; vector node; vector lazy; vector lazy_flag; function merge_node; function apply_lazy_value; function update_lazy_value; function create_lazy_value; function prop_lazy_value; public: LazySegmentTree(const vector &v, const T &init_node, const L &init_lazy, const decltype(merge_node) &merge_node, const decltype(apply_lazy_value) &apply_lazy_value, const decltype(update_lazy_value) &update_lazy_value, const decltype(create_lazy_value) &create_lazy_value, const decltype(prop_lazy_value) &prop_lazy_value = [](L v) { return v; }) : init_node(init_node), init_lazy(init_lazy), merge_node(merge_node), apply_lazy_value(apply_lazy_value), update_lazy_value(update_lazy_value), create_lazy_value(create_lazy_value), prop_lazy_value(prop_lazy_value) { ll tmp = 1; while(tmp < v.size()) tmp *= 2; N = tmp; node.resize(2 * N - 1, init_node); lazy.resize(2 * N - 1, init_lazy); lazy_flag.resize(2 * N - 1, false); for(ll i = 0; i < v.size(); i++) { node[i + N - 1] = v[i]; } for(ll i = N - 2; 0 <= i; i--) { node[i] = merge_node(node[i * 2 + 1], node[i * 2 + 2]); } } /* * node[pos] -> [left, right) */ void lazy_eval(ll pos, ll left, ll right) { if(!lazy_flag[pos]) { return; } node[pos] = apply_lazy_value(node[pos], lazy[pos]); lazy_flag[pos] = false; /* * whether the node is the bottom of tree or not. */ if(right - left > 1) { for(ll idx = 2 * pos + 1; idx <= 2 * pos + 2; idx++) { lazy[idx] = update_lazy_value(lazy[idx], prop_lazy_value(lazy[pos])); lazy_flag[idx] = true; } } lazy[pos] = init_lazy; } /* * If you want to call this func from out of class, in many cases you don't have to change the args pos, node_left, node_right. * Be careful that the range is half-open interval. * [left, right), [node_left, node_right) * @param left: lower limit of interval of query * @param right: upper limit of interval of query * @param val: the value gave from query * @param node_left: lower limit of interval of the node points. * @param node_right: upper limit of interval of the node points. */ void update_query(ll left, ll right, L val, ll pos = 0, ll node_left = 0, ll node_right = -1) { if(node_right < 0) { node_right = N; } /* * Execute lazy evaluation. */ lazy_eval(pos, node_left, node_right); /* * If the node is out of inrerval, return. */ if(right <= node_left || node_right <= left) { return; } /* * If the node cover the interval complety, update this->lazy and execute lazy_eval. * Else recursion. */ if(left <= node_left && node_right <= right) { lazy[pos] = create_lazy_value(node_left, node_right, val); lazy_flag[pos] = true; lazy_eval(pos, node_left, node_right); } else { /* * recursion */ update_query(left, right, val, 2 * pos + 1, node_left, (node_left + node_right) / 2); update_query(left, right, val, 2 * pos + 2, (node_left + node_right) / 2, node_right); node[pos] = merge_node(node[2 * pos + 1], node[2 * pos + 2]); } } T get_query(ll left, ll right, ll pos = 0, ll node_left = 0, ll node_right = -1) { if(node_right < 0) { node_right = N; } /* * Evaluate the node[pos] */ lazy_eval(pos, node_left, node_right); if(node_right <= left || right <= node_left) { return init_node; } if(left <= node_left && node_right <= right) { return node[pos]; } ll split = (node_left + node_right) / 2; return merge_node(get_query(left, right, 2 * pos + 1, node_left, split), get_query(left, right, 2 * pos + 2, split, node_right)); } }; VV edges; #define VERIFY #ifdef VERIFY int main() { ll N; cin >> N; edges.resize(N); for(ll i = 1; i < N; i++) { ll u, v; cin >> u >> v; u--; v--; edges[u].push_back(v); edges[v].push_back(u); } HeavyLightDecomposition> hld(edges); hld.decompose(); LazySegmentTree lst(V(N, 1), 0, 0, [](ll a, ll b) { return a + b; }, [](ll a, ll b) { return a + b; }, [](ll a, ll b) { return a + b; }, [](ll l, ll r, ll v) { return (r - l) * v; }, [](ll v) { return v / 2; }); auto update = [&](ll a, ll b) { lst.update_query(a, b, 1); }; auto calc_tax = [&](ll a, ll b) { return lst.get_query(a, b); }; auto merge = [&](ll a, ll b) { return a + b; }; ll Q; cin >> Q; ll ans = 0; while(Q--) { ll a, b; cin >> a >> b; a--; b--; ll val = hld.query(a, b, calc_tax, 0, merge); ans += val; hld.query(a, b, update); } cout << ans << endl; return 0; } #endif