11 LcaVertex(
const vector<vector<
int>>& g,
const vector<Type>& v,
int root=0) {
15 par=vector<vector<
int>>(k,vector<
int>(n,-1)),dep=vector<
int>(n),dat=vector<vector<Type>>(k,vector<Type>(n,Monoid::id()));
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]]);
25 if(dep[u]>dep[v]) swap(u,v);
26 Type ret=Monoid::id();
27 while(dep[u]<dep[v]) {
29 while(dep[v]-dep[u]>=(1<<(k+1))) k++;
30 ret=Monoid::op(ret,dat[k][v]),v=par[k][v];
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];
38 ret=Monoid::op(ret,dat[0][u]);