This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "https://yukicoder.me/problems/no/399" #include <vector> #include <iostream> #include <cassert> #include <map> #include <algorithm> #include <stack> #include <numeric> #include <array> using namespace std; #include "../../lib/40-graph/Graph.cpp" #include "../../lib/40-graph/StaticTree.cpp" #include "../../lib/10-segment-tree/LazySegmentTree.cpp" #include "../../lib/99-operator/monoid-lazy/MonoidRangeFoldSumRangeOperateAdd.cpp" int main(void){ int N; cin >> N; Graph<int> g(N); for(int i=0;i<N-1;++i) { int u,v; cin >> u >> v; u--,v--; g.make_bidirectional_edge(u,v,1); } auto tree = StaticTree<StaticTreeOperator<int>>::builder(g).root(0).parent().child().subtree_size().heavy_light_decomposition().build(); LazySegmentTree<MonoidRangeFoldSumRangeOperateAdd<long long,long long>> seg(N); int Q; cin >> Q; long long ans = 0; while(Q--) { int a,b; cin >> a >> b; a--,b--; auto vp = tree.vertex_set_on_path(a,b); for(auto& p:vp) { int l = p.first, r = p.second+1; int n = r-l; ans += seg.fold(l,r)+n; seg.operate(l,r,1); } } cout << ans << endl; return 0; }
#line 1 "test/graph/Tree-hld-vertex-1.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/399" #include <vector> #include <iostream> #include <cassert> #include <map> #include <algorithm> #include <stack> #include <numeric> #include <array> using namespace std; #line 1 "lib/40-graph/Graph.cpp" /* * @title Graph * @docs md/graph/Graph.md */ template<class T> class Graph{ private: const size_t N,H,W; public: vector<vector<pair<size_t,T>>> edges; Graph(const size_t N):H(-1),W(-1),N(N), edges(N) {} Graph(const size_t H, const size_t W):H(H),W(W),N(H*W), edges(H*W) {} inline void make_edge(size_t from, size_t to, T w) { edges[from].emplace_back(to,w); } //{from_y,from_x} -> {to_y,to_x} inline void make_edge(pair<size_t,size_t> from, pair<size_t,size_t> to, T w) { make_edge(from.first*W+from.second,to.first*W+to.second,w); } inline void make_bidirectional_edge(size_t from, size_t to, T w) { make_edge(from,to,w); make_edge(to,from,w); } inline void make_bidirectional_edge(pair<size_t,size_t> from, pair<size_t,size_t> to, T w) { make_edge(from.first*W+from.second,to.first*W+to.second,w); make_edge(to.first*W+to.second,from.first*W+from.second,w); } inline size_t size(){return N;} inline size_t idx(pair<size_t,size_t> yx){return yx.first*W+yx.second;} }; #line 1 "lib/40-graph/StaticTree.cpp" /* * @title StaticTree - 木 * @docs md/graph/StaticTree.md */ template<class Operator> class StaticTreeBuilder; template<class Operator> class StaticTree { private: using TypeEdge = typename Operator::TypeEdge; size_t num; size_t ord; Graph<TypeEdge>& g; friend StaticTreeBuilder<Operator>; StaticTree(Graph<TypeEdge>& graph): g(graph), num(graph.size()), depth(graph.size(),-1), order(graph.size()), edge_dist(graph.size()){ } //for make_depth void dfs(int curr, int prev){ for(const auto& e:g.edges[curr]){ const int& next = e.first; if(next==prev) continue; depth[next] = depth[curr] + 1; edge_dist[next] = Operator::func_edge_merge(edge_dist[curr],e.second); dfs(next,curr); order[ord++] = next; } } //for make_eulertour void dfs(int from){ eulertour.push_back(from); for(auto& e:child[from]){ int to = e.first; dfs(to); eulertour.push_back(from); } } void make_root(const int root) { depth[root] = 0; edge_dist[root] = Operator::unit_edge; ord = 0; dfs(root,-1); order[ord++] = root; reverse_copy(order.begin(),order.end(),back_inserter(reorder)); } void make_root() { ord = 0; for(int i=0;i<num;++i) { if(depth[i]!=-1) continue; depth[i] = 0; edge_dist[i] = Operator::unit_edge; dfs(i,-1); order[ord++] = i; } reverse_copy(order.begin(),order.end(),back_inserter(reorder)); } void make_child(const int root = 0) { child.resize(num); for (size_t i = 0; i < num; ++i) for (auto& e : g.edges[i]) if (depth[i] < depth[e.first]) child[i].push_back(e); } void make_subtree_size() { subtree_size.resize(num,1); for (size_t i:order) for (auto e : child[i]) subtree_size[i] += subtree_size[e.first]; } void make_parent() { parent.resize(num,make_pair(num,Operator::unit_edge)); for (size_t i = 0; i < num; ++i) for (auto& e : g.edges[i]) if (depth[i] > depth[e.first]) parent[i] = e; } void make_ancestor() { ancestor.resize(num); for (size_t i = 0; i < num; ++i) ancestor[i][0] = (parent[i].first!=num?parent[i]:make_pair(i,Operator::unit_lca_edge)); for (size_t j = 1; j < Operator::bit; ++j) { for (size_t i = 0; i < num; ++i) { size_t k = ancestor[i][j - 1].first; ancestor[i][j] = Operator::func_lca_edge_merge(ancestor[k][j - 1],ancestor[i][j - 1]); } } } pair<size_t,TypeEdge> lca_impl(size_t l, size_t r) { if (depth[l] < depth[r]) swap(l, r); int diff = depth[l] - depth[r]; auto ancl = make_pair(l,Operator::unit_lca_edge); auto ancr = make_pair(r,Operator::unit_lca_edge); for (int j = 0; j < Operator::bit; ++j) { if (diff & (1 << j)) ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][j],ancl); } if(ancl.first==ancr.first) return ancl; for (int j = Operator::bit - 1; 0 <= j; --j) { if(ancestor[ancl.first][j].first!=ancestor[ancr.first][j].first) { ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][j],ancl); ancr = Operator::func_lca_edge_merge(ancestor[ancr.first][j],ancr); } } ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][0],ancl); ancr = Operator::func_lca_edge_merge(ancestor[ancr.first][0],ancr); return Operator::func_lca_edge_merge(ancl,ancr); } pair<TypeEdge,vector<size_t>> diameter_impl() { StaticTree tree = StaticTree::builder(g).build(); size_t root = 0; { tree.make_root(0); } root = max_element(tree.edge_dist.begin(),tree.edge_dist.end()) - tree.edge_dist.begin(); { tree.make_root(root); } size_t leaf = max_element(tree.edge_dist.begin(),tree.edge_dist.end()) - tree.edge_dist.begin(); TypeEdge sz = tree.edge_dist[leaf]; vector<size_t> st; { tree.make_parent(); while(leaf != root) { st.push_back(leaf); leaf = tree.parent[leaf].first; } st.push_back(root); } return make_pair(sz,st); } template<class TypeReroot> vector<TypeReroot> rerooting_impl(vector<TypeReroot> rerootdp,vector<TypeReroot> rerootparent) { for(size_t pa:order) for(auto& e:child[pa]) rerootdp[pa] = Operator::func_reroot_dp(rerootdp[pa],rerootdp[e.first]); for(size_t pa:reorder) { if(depth[pa]) rerootdp[pa] = Operator::func_reroot_dp(rerootdp[pa],rerootparent[pa]); size_t m = child[pa].size(); for(int j = 0; j < m && depth[pa]; ++j){ size_t ch = child[pa][j].first; rerootparent[ch] = Operator::func_reroot_dp(rerootparent[ch],rerootparent[pa]); } if(m <= 1) continue; vector<TypeReroot> l(m),r(m); for(int j = 0; j < m; ++j) { size_t ch = child[pa][j].first; l[j] = rerootdp[ch]; r[j] = rerootdp[ch]; } for(int j = 1; j+1 < m; ++j) l[j] = Operator::func_reroot_merge(l[j],l[j-1]); for(int j = m-2; 0 <=j; --j) r[j] = Operator::func_reroot_merge(r[j],r[j+1]); size_t chl = child[pa].front().first; size_t chr = child[pa].back().first; rerootparent[chl] = Operator::func_reroot_dp(rerootparent[chl],r[1]); rerootparent[chr] = Operator::func_reroot_dp(rerootparent[chr],l[m-2]); for(int j = 1; j+1 < m; ++j) { size_t ch = child[pa][j].first; rerootparent[ch] = Operator::func_reroot_dp(rerootparent[ch],l[j-1]); rerootparent[ch] = Operator::func_reroot_dp(rerootparent[ch],r[j+1]); } } return rerootdp; } void make_eulertour() { dfs(reorder.front()); eulertour_range.resize(num); for(int i = 0; i < eulertour.size(); ++i) eulertour_range[eulertour[i]].second = i+1; for(int i = eulertour.size()-1; 0 <= i; --i) eulertour_range[eulertour[i]].first = i; } void make_heavy_light_decomposition(){ head.resize(num); hld.resize(num); iota(head.begin(),head.end(),0); for(size_t& pa:reorder) { pair<size_t,size_t> maxi = {0,num}; for(auto& p:child[pa]) maxi = max(maxi,{subtree_size[p.first],p.first}); if(maxi.first) head[maxi.second] = head[pa]; } stack<size_t> st_head,st_sub; size_t cnt = 0; //根に近い方から探索 for(size_t& root:reorder){ if(depth[root]) continue; //根をpush st_head.push(root); while(st_head.size()){ size_t h = st_head.top(); st_head.pop(); //部分木の根をpush st_sub.push(h); while (st_sub.size()){ size_t pa = st_sub.top(); st_sub.pop(); //部分木をカウントしていく hld[pa] = cnt++; //子を探索 for(auto& p:child[pa]) { //子のheadが親と同じなら、そのまま進む if(head[p.first]==head[pa]) st_sub.push(p.first); //そうじゃない場合は、そこから新しく部分木としてみなす else st_head.push(p.first); } } } } } //type 0: vertex, 1: edge vector<pair<size_t,size_t>> path_impl(size_t u,size_t v,int type = 0) { vector<pair<size_t,size_t>> path; while(1){ if(hld[u]>hld[v]) swap(u,v); if(head[u]!=head[v]) { path.push_back({hld[head[v]],hld[v]}); v=parent[head[v]].first; } else { path.push_back({hld[u],hld[v]}); break; } } reverse(path.begin(),path.end()); if(type) path.front().first++; return path; } pair<vector<pair<size_t,size_t>>,vector<pair<size_t,size_t>>> ordered_path_impl(size_t u,size_t v,int type = 0) { vector<pair<size_t,size_t>> path_lca_to_u; vector<pair<size_t,size_t>> path_lca_to_v; while(1){ if(head[u] == head[v]) { if(depth[u] < depth[v]) path_lca_to_v.emplace_back(hld[u]+type,hld[v]); else path_lca_to_u.emplace_back(hld[v]+type,hld[u]); break; } else if(hld[u] < hld[v]) { path_lca_to_v.emplace_back(hld[head[v]],hld[v]); v = parent[head[v]].first; } else if(hld[u] > hld[v]) { path_lca_to_u.emplace_back(hld[head[u]],hld[u]); u = parent[head[u]].first; } } reverse(path_lca_to_v.begin(),path_lca_to_v.end()); return {path_lca_to_u,path_lca_to_v}; } size_t lca_idx_impl(size_t u,size_t v){ while(1){ if(hld[u]>hld[v]) swap(u,v); if(head[u]==head[v]) return u; v=parent[head[v]].first; } } vector<size_t> head; public: vector<size_t> depth; vector<size_t> order; vector<size_t> reorder; vector<size_t> subtree_size; vector<pair<size_t,TypeEdge>> parent; vector<vector<pair<size_t,TypeEdge>>> child; vector<TypeEdge> edge_dist; vector<array<pair<size_t,TypeEdge>,Operator::bit>> ancestor; vector<size_t> eulertour; vector<pair<size_t,size_t>> eulertour_range; vector<size_t> hld; /** * O(N) builder */ static StaticTreeBuilder<Operator> builder(Graph<TypeEdge>& graph) { return StaticTreeBuilder<Operator>(graph);} /** * O(logN) after make_ancestor * return {lca,lca_dist} l and r must be connected */ pair<size_t,TypeEdge> lca(size_t l, size_t r) {return lca_impl(l,r);} /** * O(N) anytime * return {diameter size,diameter set} */ pair<TypeEdge,vector<size_t>> diameter(void){return diameter_impl();} /** * O(N) after make_child */ template<class TypeReroot> vector<TypeReroot> rerooting(const vector<TypeReroot>& rerootdp,const vector<TypeReroot>& rerootparent) {return rerooting_impl(rerootdp,rerootparent);} /** * O(logN) */ vector<pair<size_t,size_t>> vertex_set_on_path(size_t u, size_t v) {return path_impl(u,v,0);} /** /** * O(logN) */ vector<pair<size_t,size_t>> edge_set_on_path(size_t u, size_t v) {return path_impl(u,v,1);} /** * O(logN) * {lca to u path,lca to v path} */ pair<vector<pair<size_t,size_t>>,vector<pair<size_t,size_t>>> vertex_ordered_set_on_path(size_t u, size_t v) {return ordered_path_impl(u,v,0);} /** * O(logN) * {lca to u path,lca to v path} */ pair<vector<pair<size_t,size_t>>,vector<pair<size_t,size_t>>> edge_ordered_set_on_path(size_t u, size_t v) {return ordered_path_impl(u,v,1);} /** * O(logN) ancestorのlcaより定数倍軽め。idxだけ */ size_t lca_idx(size_t u, size_t v) {return lca_idx_impl(u,v);} }; template<class Operator> class StaticTreeBuilder { bool is_root_made =false; bool is_child_made =false; bool is_parent_made=false; bool is_subtree_size_made=false; public: using TypeEdge = typename Operator::TypeEdge; StaticTreeBuilder(Graph<TypeEdge>& g):tree(g){} StaticTreeBuilder& root(const int rt) { is_root_made=true; tree.make_root(rt); return *this;} StaticTreeBuilder& root() { is_root_made=true; tree.make_root(); return *this;} StaticTreeBuilder& child() { assert(is_root_made); is_child_made=true; tree.make_child(); return *this;} StaticTreeBuilder& parent() { assert(is_root_made); is_parent_made=true; tree.make_parent(); return *this;} StaticTreeBuilder& subtree_size() { assert(is_child_made); is_subtree_size_made=true; tree.make_subtree_size(); return *this;} StaticTreeBuilder& ancestor() { assert(is_parent_made); tree.make_ancestor(); return *this;} StaticTreeBuilder& eulertour() { assert(is_child_made); tree.make_eulertour(); return *this;} StaticTreeBuilder& heavy_light_decomposition() { assert(is_subtree_size_made); assert(is_parent_made); tree.make_heavy_light_decomposition(); return *this;} StaticTree<Operator>&& build() {return move(tree);} private: StaticTree<Operator> tree; }; template<class T> struct StaticTreeOperator{ using TypeEdge = T; inline static constexpr size_t bit = 20; inline static constexpr TypeEdge unit_edge = 0; inline static constexpr TypeEdge unit_lca_edge = 0; inline static constexpr TypeEdge func_edge_merge(const TypeEdge& parent,const TypeEdge& w){return parent+w;} inline static constexpr pair<size_t,TypeEdge> func_lca_edge_merge(const pair<size_t,TypeEdge>& l,const pair<size_t,TypeEdge>& r){return make_pair(l.first,l.second+r.second);} template<class TypeReroot> inline static constexpr TypeReroot func_reroot_dp(const TypeReroot& l,const TypeReroot& r) {return {l.first+r.first+r.second,l.second+r.second};} template<class TypeReroot> inline static constexpr TypeReroot func_reroot_merge(const TypeReroot& l,const TypeReroot& r) {return {l.first+r.first,l.second+r.second};} }; //auto tree = StaticTree<StaticTreeOperator<int>>::builder(g).build(); #line 1 "lib/10-segment-tree/LazySegmentTree.cpp" /* * @title LazySegmentTree - 非再帰抽象化遅延評価セグメント木 * @docs md/segment-tree/LazySegmentTree.md */ template<class Monoid> class LazySegmentTree { using TypeNode = typename Monoid::TypeNode; using TypeLazy = typename Monoid::TypeLazy; size_t num; size_t length; size_t height; vector<TypeNode> node; vector<TypeLazy> lazy; vector<pair<size_t,size_t>> range; void propagate(int k) { if(lazy[k] == Monoid::unit_lazy) return; node[k] = Monoid::func_operate(node[k],lazy[k],range[k].first,range[k].second); if(k < length) lazy[2*k+0] = Monoid::func_lazy(lazy[2*k+0],lazy[k]); if(k < length) lazy[2*k+1] = Monoid::func_lazy(lazy[2*k+1],lazy[k]); lazy[k] = Monoid::unit_lazy; } void build() { for (int i = length - 1; i >= 0; --i) node[i] = Monoid::func_fold(node[(i<<1)+0],node[(i<<1)+1]); range.resize(2 * length); for (int i = 0; i < length; ++i) range[i+length] = make_pair(i,i+1); for (int i = length - 1; i >= 0; --i) range[i] = make_pair(range[(i<<1)+0].first,range[(i<<1)+1].second); } public: //unitで初期化 LazySegmentTree(const size_t num) : num(num) { for (length = 1,height = 0; length <= num; length *= 2, height++); node.resize(2 * length, Monoid::unit_node); lazy.resize(2 * length, Monoid::unit_lazy); for (int i = 0; i < num; ++i) node[i + length] = Monoid::unit_node; build(); } // //同じinitで初期化 LazySegmentTree(const size_t num, const TypeNode init) : num(num) { for (length = 1,height = 0; length <= num; length *= 2, height++); node.resize(2 * length, Monoid::unit_node); lazy.resize(2 * length, Monoid::unit_lazy); for (int i = 0; i < num; ++i) node[i + length] = init; build(); } //vectorで初期化 LazySegmentTree(const vector<TypeNode>& vec) : num(vec.size()) { for (length = 1,height = 0; length <= vec.size(); length *= 2, height++); node.resize(2 * length, Monoid::unit_node); lazy.resize(2 * length, Monoid::unit_lazy); for (int i = 0; i < vec.size(); ++i) node[i + length] = vec[i]; build(); } //operate [a,b) void operate(int a, int b, TypeLazy x) { int l = a + length, r = b + length - 1; for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i); for(r++; l < r; l >>=1, r >>=1) { if(l&1) lazy[l] = Monoid::func_lazy(lazy[l],x), propagate(l),l++; if(r&1) --r,lazy[r] = Monoid::func_lazy(lazy[r],x), propagate(r); } l = a + length, r = b + length - 1; while ((l>>=1),(r>>=1),l) { if(lazy[l] == Monoid::unit_lazy) node[l] = Monoid::func_fold(Monoid::func_operate(node[(l<<1)+0],lazy[(l<<1)+0],range[(l<<1)+0].first,range[(l<<1)+0].second),Monoid::func_operate(node[(l<<1)+1],lazy[(l<<1)+1],range[(l<<1)+1].first,range[(l<<1)+1].second)); if(lazy[r] == Monoid::unit_lazy) node[r] = Monoid::func_fold(Monoid::func_operate(node[(r<<1)+0],lazy[(r<<1)+0],range[(r<<1)+0].first,range[(r<<1)+0].second),Monoid::func_operate(node[(r<<1)+1],lazy[(r<<1)+1],range[(r<<1)+1].first,range[(r<<1)+1].second)); } } //fold [a,b) TypeNode fold(int a, int b) { int l = a + length, r = b + length - 1; for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i); TypeNode vl = Monoid::unit_node, vr = Monoid::unit_node; for(r++; l < r; l >>=1, r >>=1) { if(l&1) vl = Monoid::func_fold(vl,Monoid::func_operate(node[l],lazy[l],range[l].first,range[l].second)),l++; if(r&1) r--,vr = Monoid::func_fold(Monoid::func_operate(node[r],lazy[r],range[r].first,range[r].second),vr); } return Monoid::func_fold(vl,vr); } //return [0,length] int prefix_binary_search(TypeNode var) { int l = length, r = 2*length - 1; for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i); if(!Monoid::func_check(node[1],var)) return num; TypeNode ret = Monoid::unit_node; size_t idx = 2; for(; idx < 2*length; idx<<=1){ if(!Monoid::func_check(Monoid::func_fold(ret,Monoid::func_operate(node[idx],lazy[idx],range[idx].first,range[idx].second)),var)) { ret = Monoid::func_fold(ret,Monoid::func_operate(node[idx],lazy[idx],range[idx].first,range[idx].second)); idx++; } } return min((idx>>1) - length,num); } //range[l,r) return [l,r] int binary_search(size_t l, size_t r, TypeNode var) { if (l < 0 || length <= l || r < 0 || length < r) return -1; for (int i = height; 0 < i; --i) propagate((l+length) >> i), propagate((r+length-1) >> i); TypeNode ret = Monoid::unit_node; size_t off = l; for(size_t idx = l+length; idx < 2*length && off < r; ){ if(range[idx].second<=r && !Monoid::func_check(Monoid::func_fold(ret,Monoid::func_operate(node[idx],lazy[idx],range[idx].first,range[idx].second)),var)) { ret = Monoid::func_fold(ret,Monoid::func_operate(node[idx],lazy[idx],range[idx].first,range[idx].second)); off = range[idx++].second; if(!(idx&1)) idx >>= 1; } else{ idx <<=1; } } return off; } void print(){ // cout << "node" << endl; // for(int i = 1,j = 1; i < 2*length; ++i) { // cout << node[i] << " "; // if(i==((1<<j)-1) && ++j) cout << endl; // } // cout << "lazy" << endl; // for(int i = 1,j = 1; i < 2*length; ++i) { // cout << lazy[i] << " "; // if(i==((1<<j)-1) && ++j) cout << endl; // } cout << "vector" << endl; cout << "{ " << fold(0,1); for(int i = 1; i < length; ++i) cout << ", " << fold(i,i+1); cout << " }" << endl; } }; #line 1 "lib/99-operator/monoid-lazy/MonoidRangeFoldSumRangeOperateAdd.cpp" /* * @title MonoidRangeSumRangeAdd - fold:区間和, opearate:区間加算 * @docs md/operator/monoid-lazy/MonoidRangeSumRangeAdd.md */ template<class T, class U> struct MonoidRangeFoldSumRangeOperateAdd { using TypeNode = T; using TypeLazy = U; inline static constexpr TypeNode unit_node = 0; inline static constexpr TypeLazy unit_lazy = 0; inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return l+r;} inline static constexpr TypeLazy func_lazy(TypeLazy old_lazy,TypeLazy new_lazy){return old_lazy+new_lazy;} inline static constexpr TypeNode func_operate(TypeNode node,TypeLazy lazy,int l, int r){return node+lazy*(r-l);} inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var <= nodeVal;} }; #line 16 "test/graph/Tree-hld-vertex-1.test.cpp" int main(void){ int N; cin >> N; Graph<int> g(N); for(int i=0;i<N-1;++i) { int u,v; cin >> u >> v; u--,v--; g.make_bidirectional_edge(u,v,1); } auto tree = StaticTree<StaticTreeOperator<int>>::builder(g).root(0).parent().child().subtree_size().heavy_light_decomposition().build(); LazySegmentTree<MonoidRangeFoldSumRangeOperateAdd<long long,long long>> seg(N); int Q; cin >> Q; long long ans = 0; while(Q--) { int a,b; cin >> a >> b; a--,b--; auto vp = tree.vertex_set_on_path(a,b); for(auto& p:vp) { int l = p.first, r = p.second+1; int n = r-l; ans += seg.fold(l,r)+n; seg.operate(l,r,1); } } cout << ans << endl; return 0; }