建树
结点数为N 边数为M 根节点S
log2N 为树的最大深度
int log2N=log(1.0*N)/log(2.0)+0.5;
通过DFS预处理出树与深度
inline void dfs(int x,int f){
V[x]=1;
D[x]=D[f]+1;
F[X][0]=f;
for(int i=Last[x];i;i=e[i].next){
if(V[x]) continue;
dfs(e[i].to,x);
}
}
朴素算法
DFS
复杂度O(N)
求LCA(A,B)
从A点DFS到根S,路径标记为为1
再尝试从B点DFS到根S 路径上第一个被标记为1的点即为所求
调点
设u,v中深度大的点为u
寻找u点与v点同一深度的祖先
查看u点和v点的父节点是否相同
相同返回父节点
不相同u与v变成各自的父节点(上提)
inline int LCA(int u,int v){
if(D[u]<D[v])
swap(u,v);
while(D[u]>D[v])
u=fa[u];
while(u!=v){
u=fa[u];
v=fa[v];
}
return u;
}
倍增 + DP (在线)
倍增:每次跳2^x^ 个点
倍增数组F[i][j]:从i点开始朝根结点 走2^j^ 步所到达的点
F[i][j]=F[F[i][j-1]][j-1]
i 跳 2^j^ 步 是 i 跳了 2^(j-1)^ 步后的点再跳 2^(j-1)^ 步所到的点
2^j^=2*2^(j-1)^ 其中j<=log~2~N d[i]>=2^j^
for(int j=1;j<=log2n;++j)
for(int i=1;i<=n;++i)
if(d[i]>=(1<<j))
f[i][j]=f[f[i][j-1]][j-1];
求LCA(X,Y)
设此时 D[X] > D[Y]
将 X 提到与 Y 同一深度的位置
即 X 在自己的祖先中 寻找一个与 Y 同一深度的祖先 T
for(int i=Log2N;i>=0;--i)
if(D[X]>=D[Y])
X=F[X][i];
如果 T == Y 那么 LCA(X,Y)=Y;
if(X==Y) return X;
如果 T != Y 那么 LCA(X,Y)=LCA(T,Y)
若求 X 与 Y 的公共祖先,只用求 T 与 Y 的公共祖先
for(int i=Log2N;i>=0;--i)
if(F[X][i]!=F[Y][i])
X=F[X][i],Y=F[Y][i];
return F[X][0];
Tarjan (离线)
懒得写了
0 条评论