1, 倍增
- vector<int>p[maxn];
- int dep[maxn],f[maxn][20];//f[i][0] 保存 i 的父亲
- inline void dfs(int u,int fa,int d)
- {
- dep[u]=d;f[u][0]=fa;
- for(int i=0;i<p[u].size();i++)
- {
- int v=p[u][i];
- if(v==fa)continue;
- dfs(v,u,d+1);
- }
- }
- inline void init(int n)
- {
- for(int j=1;(1<<j)<=n;j++)
- for(int i=1;i<=n;i++)
- if(f[i][j-1])f[i][j]=f[f[i][j-1]][j-1];
- //i 的第 2^j 祖先就是 i 的第 2^(j-1) 祖先的第 2^(j-1) 祖先
- }
- inline int LCA(int u,int v)
- {
- int i=0,j;
- if(dep[u]<dep[v])swap(u,v);
- for(i=1;(1<<i)<=dep[u];i++);i--;// 缩小 j 的范围 不缩小则 j 从 20 左右开始递减
- // 使 a,b 两点的深度相同
- for(j=i;j>=0;j--)
- if(dep[u]-(1<<j)>=dep[v])u=f[u][j];
- if(u==v)return u;
- for(j=i;j>=0;j--)
- {
- if(f[u][j]!=-1&&f[u][j]!=f[v][j])
- {
- u=f[u][j];
- v=f[v][j];
- }
- }
- return f[u][0];
- }
2, 树链剖分
- vector<int>p[maxn];
- int siz[maxn],dep[maxn],fad[maxn],son[maxn],top[maxn],cnt;
- inline void dfs1(int u,int fa,int d)
- {
- dep[u]=d;fad[u]=fa;siz[u]=1;
- for(int i=0;i<p[u].size();i++)
- {
- int v=p[u][i];
- if(v==fa)continue;
- dfs1(v,u,d+1);
- siz[u]+=siz[v];
- if(siz[v]>siz[son[u]])son[u]=v;
- }
- }
- inline void dfs2(int u,int t)
- {
- top[u]=t;
- if(!son[u])return;// 当前节点不在重链上
- dfs2(son[u],t);
- for(int i=0;i<p[u].size();i++)
- {
- int v=p[u][i];
- if(v!=son[u]&&v!=fad[u])dfs2(v,v);// 非重节点的 top 是自己
- }
- }
- inline int LCA(int u,int v)
- {
- while(top[u]!=top[v])
- {
- if(dep[top[u]]<dep[top[v]])swap(u,v);
- u=fad[top[u]];
- }
- if(dep[u]>dep[v])return v;
- return u;
- }
3,st 表 (最快
- vector<int>p[maxn];
- int depth[maxn<<1],id[maxn],rid[maxn<<1],cnt,st[maxn<<1][25];
- inline void dfs(int u,int fa,int d)
- {
- id[u]=++cnt;rid[cnt]=u;depth[cnt]=d;
- for(int i=0;i<p[u].size();i++)
- {
- if(p[u][i]==fa)continue;
- dfs(p[u][i],u,d+1);
- rid[++cnt]=u;depth[cnt]=d;
- }
- }
- int lg[maxn<<1];
- inline void init()
- {
- lg[0]=-1;
- for(int i=1;i<=cnt;i++)lg[i]=lg[i>>1]+1;
- for(int i=1;i<=cnt;i++)st[i][0]=i;
- for(int j=1;(1<<j)<=cnt;j++)
- for(int i=1;i+(1<<j)-1<=cnt;i++)
- st[i][j]=depth[st[i][j-1]]<depth[st[i+(1<<j-1)][j-1]]?
- st[i][j-1]:
- st[i+(1<<j-1)][j-1];
- }
- inline int LCA(int u,int v)
- {
- if(id[u]>id[v])swap(u,v);
- int s=id[u],t=id[v],len=lg[t-s+1];
- return depth[st[s][len]]<depth[st[t-(1<<len)+1][len]]?rid[st[s][len]]:rid[st[t-(1<<len)+1][len]];
- }
来源: http://www.bubuko.com/infodetail-3416869.html