This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#include "Graph2/HeavyLightDecomposition.hpp"
HLD
コードに書いてある G[i][0] : iから子へと伸びるHeavy Edge となるように並び替えているので, HLD構築時に渡したgとhld.gは構築後に異なる
#include "./GraphTemplate.hpp" /* ref : https://ferin-tech.hatenablog.com/entry/2019/11/21/HL%E5%88%86%E8%A7%A3%E3%81%AE%E5%AE%9F%E8%A3%85 https://ei1333.github.io/library/graph/tree/heavy-light-decomposition.hpp HLD 各頂点から頂点を扱いやすいように並び替えた時の番号への写像を考える ! 辺属性で考えたい場合 頂点iから親方向に伸びている辺をpos[i]にSegment木などにセットし,各メソッドをedge=trueで扱う member head[i] : iの先頭 in[i], out[i] : i頂点以下の部分木のin, out method lca(u, v) : least common ancestor dist(u, v) : 距離 get_path(u, v) : 区間のvectorを返すので各区間でクエリを処理し,mergeすればよい get_subtree(u) : 部分木にあたる区間を返す pos(u) : 並び替えをした後,頂点uがどの場所へ移るかの射影 */ template<typename T> struct HeavyLightDecomposition{ private: void dfs1(int pre,int cur){ par[cur]=pre; sz[cur]=1; if(!g[cur].empty() and g[cur][0]==pre) swap(g[cur][0],g[cur].back()); for(auto &e:g[cur])if(e!=pre){ dis[e]+=dis[cur]+e.w; dfs1(cur,e); sz[cur]+=sz[e]; if(sz[g[cur][0]]<sz[e]) swap(g[cur][0],e); } } void dfs2(int pre,int cur,int &t){ in[cur]=t++; rev[in[cur]]=cur; for(auto &e:g[cur])if(e!=pre){ head[e]=(g[cur][0]==e?head[cur]:e); dfs2(cur,e,t); } out[cur]=t; } public: Graph<T> g; vector<int> sz,in,out,head,rev,par; vector<T> dis; HeavyLightDecomposition(Graph<T> g,int root=0): g(g),sz(g.V,0),in(g.V,0),out(g.V,0),head(g.V,0),rev(g.V,0),par(g.V,0),dis(g.V,0){ dfs1(-1,root); int t=0; dfs2(-1,root,t); } int la(int v,int k){ for(;;){ int u=head[v]; if(in[v]-k>=in[u]) return rev[in[v]-k]; k-=in[v]-in[u]+1; v=par[u]; } } int lca(int u,int v){ for(;;v=par[head[v]]){ // 深い方から上げていく if(in[u]>in[v]) swap(u,v); if(head[u]==head[v]) return u; } } T dist(int u,int v){ return dis[u]+dis[v]-dis[lca(u,v)]*2; } // return ranges vector<pair<int,int>> get_path(int u,int v,bool edge=false){ vector<pair<int,int>> ret; for(;;v=par[head[v]]){ if(in[u]>in[v]) swap(u,v); if(head[u]==head[v]) break; ret.emplace_back(in[head[v]],in[v]+1); } // 最後の区間の始点がLCA ret.emplace_back(in[u]+edge,in[v]+1); return ret; } // return one range pair<int,int> get_subtree(int u,bool edge=false){ return {in[u]+edge,out[u]}; } int pos(int u){ return in[u]; } };
#line 1 "Graph2/GraphTemplate.hpp" // graph template // ref : https://ei1333.github.io/library/graph/graph-template.hpp template<typename T=int> struct Edge{ int from,to; T w; int idx; Edge()=default; Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){} operator int() const{return to;} }; template<typename T=int> struct Graph{ vector<vector<Edge<T>>> g; int V,E; Graph()=default; Graph(int n):g(n),V(n),E(0){} int size(){ return (int)g.size(); } void resize(int k){ g.resize(k); V=k; } inline const vector<Edge<T>> &operator[](int k)const{ return (g.at(k)); } inline vector<Edge<T>> &operator[](int k){ return (g.at(k)); } void add_directed_edge(int from,int to,T cost=1){ g[from].emplace_back(from,to,cost,E++); } void add_edge(int from,int to,T cost=1){ g[from].emplace_back(from,to,cost,E); g[to].emplace_back(to,from,cost,E++); } void read(int m,int pad=-1,bool weighted=false,bool directed=false){ for(int i=0;i<m;i++){ int u,v;cin>>u>>v; u+=pad,v+=pad; T w=T(1); if(weighted) cin>>w; if(directed) add_directed_edge(u,v,w); else add_edge(u,v,w); } } }; #line 2 "Graph2/HeavyLightDecomposition.hpp" /* ref : https://ferin-tech.hatenablog.com/entry/2019/11/21/HL%E5%88%86%E8%A7%A3%E3%81%AE%E5%AE%9F%E8%A3%85 https://ei1333.github.io/library/graph/tree/heavy-light-decomposition.hpp HLD 各頂点から頂点を扱いやすいように並び替えた時の番号への写像を考える ! 辺属性で考えたい場合 頂点iから親方向に伸びている辺をpos[i]にSegment木などにセットし,各メソッドをedge=trueで扱う member head[i] : iの先頭 in[i], out[i] : i頂点以下の部分木のin, out method lca(u, v) : least common ancestor dist(u, v) : 距離 get_path(u, v) : 区間のvectorを返すので各区間でクエリを処理し,mergeすればよい get_subtree(u) : 部分木にあたる区間を返す pos(u) : 並び替えをした後,頂点uがどの場所へ移るかの射影 */ template<typename T> struct HeavyLightDecomposition{ private: void dfs1(int pre,int cur){ par[cur]=pre; sz[cur]=1; if(!g[cur].empty() and g[cur][0]==pre) swap(g[cur][0],g[cur].back()); for(auto &e:g[cur])if(e!=pre){ dis[e]+=dis[cur]+e.w; dfs1(cur,e); sz[cur]+=sz[e]; if(sz[g[cur][0]]<sz[e]) swap(g[cur][0],e); } } void dfs2(int pre,int cur,int &t){ in[cur]=t++; rev[in[cur]]=cur; for(auto &e:g[cur])if(e!=pre){ head[e]=(g[cur][0]==e?head[cur]:e); dfs2(cur,e,t); } out[cur]=t; } public: Graph<T> g; vector<int> sz,in,out,head,rev,par; vector<T> dis; HeavyLightDecomposition(Graph<T> g,int root=0): g(g),sz(g.V,0),in(g.V,0),out(g.V,0),head(g.V,0),rev(g.V,0),par(g.V,0),dis(g.V,0){ dfs1(-1,root); int t=0; dfs2(-1,root,t); } int la(int v,int k){ for(;;){ int u=head[v]; if(in[v]-k>=in[u]) return rev[in[v]-k]; k-=in[v]-in[u]+1; v=par[u]; } } int lca(int u,int v){ for(;;v=par[head[v]]){ // 深い方から上げていく if(in[u]>in[v]) swap(u,v); if(head[u]==head[v]) return u; } } T dist(int u,int v){ return dis[u]+dis[v]-dis[lca(u,v)]*2; } // return ranges vector<pair<int,int>> get_path(int u,int v,bool edge=false){ vector<pair<int,int>> ret; for(;;v=par[head[v]]){ if(in[u]>in[v]) swap(u,v); if(head[u]==head[v]) break; ret.emplace_back(in[head[v]],in[v]+1); } // 最後の区間の始点がLCA ret.emplace_back(in[u]+edge,in[v]+1); return ret; } // return one range pair<int,int> get_subtree(int u,bool edge=false){ return {in[u]+edge,out[u]}; } int pos(int u){ return in[u]; } };