Kyopro Library
 
読み取り中…
検索中…
一致する文字列を見つけられません
lca_vertex.hpp
[詳解]
1#include "../../../kyopro_library/template.hpp"
2
3/// @brief 頂点属性 LCA
4/// @ref verify: https://onlinejudge.u-aizu.ac.jp/solutions/problem/3372/revector<int>ew/10572853/Today03/C++17
5template<typename Monoid>
6struct LcaVertex {
7 using Type=typename Monoid::Type;
8
9 /// @brief コンストラクタ
10 /// @param v 頂点の重み
11 LcaVertex(const vector<vector<int>>& g, const vector<Type>& v, int root=0) {
12 int n=g.size();
13 int k=1;
14 while((1<<k)<n) k++;
15 par=vector<vector<int>>(k,vector<int>(n,-1)),dep=vector<int>(n),dat=vector<vector<Type>>(k,vector<Type>(n,Monoid::id()));
16 dfs(g,v,root,-1);
17 for(int i=0; i<k-1; i++) for(int j=0; j<n; j++) {
18 par[i+1][j]=par[i][j]==-1?-1:par[i][par[i][j]];
19 dat[i+1][j]=par[i][j]==-1?Monoid::id():Monoid::op(dat[i][j],dat[i][par[i][j]]);
20 }
21 }
22
23 /// @brief パス u-v のモノイド積を返す
24 Type fold(int u, int v) {
25 if(dep[u]>dep[v]) swap(u,v);
26 Type ret=Monoid::id();
27 while(dep[u]<dep[v]) {
28 int k=0;
29 while(dep[v]-dep[u]>=(1<<(k+1))) k++;
30 ret=Monoid::op(ret,dat[k][v]),v=par[k][v];
31 }
32 while(u!=v) {
33 int k=0;
34 while(par[k+1][u]!=par[k+1][v]) k++;
35 ret=Monoid::op(ret,dat[k][u]),ret=Monoid::op(ret,dat[k][v]);
36 u=par[k][u],v=par[k][v];
37 }
38 ret=Monoid::op(ret,dat[0][u]);
39 return ret;
40 }
41
42private:
43 vector<vector<int>> par;
44 vector<int> dep;
45 vector<vector<Type>> dat;
46 void dfs(const vector<vector<int>>& g, const vector<Type>& v, int now, int pre) {
47 dat[0][now]=v[now]; par[0][now]=pre; dep[now]=(pre==-1 ? 0 : dep[pre]+1);
48 for(int nxt: g[now]) {
49 if(nxt==pre) continue;
50 dfs(g,v,nxt,now);
51 }
52 }
53};
54
55#include"../../../kyopro_library/others/monoid.hpp"
頂点属性 LCA verify: https://onlinejudge.u-aizu.ac.jp/solutions/problem/3372/revector<int>ew/10572853/Tod...
Definition lca_vertex.hpp:6
Type fold(int u, int v)
パス u-v のモノイド積を返す
LcaVertex(const vector< vector< int > > &g, const vector< Type > &v, int root=0)
コンストラクタ