倍增

这是最最最常见的写法了，一个fa[N][logN]的数组直接搞定

时间复杂度也不算太高

预处理 $ O(nlogn) $ 如果你想卡的话，可以卡到 $ O(nlogh) $ h为树的深度

查询 $ O(2*logn) $ 最坏，平均 $ O(logn) $

$ code $

int dfn[N],cnt;

int dep[N],fa[N][21],siz[N];

void dfs_first(int x){

	dfn[x]=++cnt;

	siz[x]=1;

	for(re i=head[x];i;i=nxt[i]){

		int y=to[i];

		if(y==fa[x][0])continue;

		fa[y][0]=x;

		for(re i=1;i<=20;i++)fa[y][i]=fa[fa[y][i-1]][i-1];//cout<<fa[y][i]<<endl;

		dep[y]=dep[x]+1;

		dfs_first(y);

		siz[x]+=siz[y];

	}

}

int LCA(int x,int y){

	if(dep[x]<dep[y])swap(x,y);

	for(re i=20;i>=0;i--)

		if(dep[fa[x][i]]>=dep[y])

			x=fa[x][i];

	if(x==y)return x;

	for(re i=20;i>=0;i--)

		if(fa[x][i]!=fa[y][i])

			x=fa[x][i],y=fa[y][i];

	return fa[x][0];

}

注意：：：：dep[1]要赋值为1,否则求取LCA时就全是0了

RMQ

这个真是神级算法了

利用RMQ的原理找到LCA

为什么呢？因为在两个点的之间，最近的公共祖先一定是，这两个点的dfs序中，深度最小的那个

这样问题就转化成了在区间上求最小值，也就是RMQ问题

最最最恐怖的是他的时间复杂度

预处理与倍增相同 $ O(nlogn) $ 不能卡到h

但是查询快爆了 $ O(1) $

$ code $

int dfn[N],cnt;

int dep[N],fa[N];

int st[N][21],lg2[N];

void dfs_first(int x){

	dfn[x]=++cnt;

	st[cnt][0]=x;

	for(re i=head[x];i;i=nxt[i]){

		int y=to[i];

		if(y==fa[x])continue;

		fa[y]=x;

		dep[y]=dep[x]+1;

		dfs_first(y);

	}

}

void get_st(){

	for(re i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;

	for(re j=1;j<=20;j++){

		for(re i=1;i+(1<<j)-1<=n;i++){

			int r=i+(1<<j-1);

			st[i][j]=dep[st[i][j-1]]<dep[st[r][j-1]]?st[i][j-1]:st[r][j-1];

		}

	}

}

int LCA(int x,int y){

	x=dfn[x];y=dfn[y];

	if(x>y)swap(x,y);

	int tmp=lg2[y-x+1];

	return dep[st[x][tmp]]<dep[st[y-(1<<tmp)+1][tmp]]?st[x][tmp]:st[y-(1<<tmp)+1][tmp];

}

所以这个还是比倍增稍微快一点的

树链剖分

这个更快不信你往下看

就是简单的根据树链剖分的top一直往上跳

我们分析一下复杂度

预处理 $ O(2*n) $ 这个完全没有争议

查询，这个查询总起来是比倍增快一些的

因为一般的题不会给你出一颗满二叉树，所以我们每次向上跳，会远远少于logh

毕竟如果每次节点都在轻链上，高度就是logn，没有争议，比倍增快

除非他卡你，就算卡你，你也是logn，快快快快爆了

所以查询的复杂度是 $ O(logn) $ 但是实际应用时，比这个快多了

$ code $

int dfn[N],cnt,fa[N];

int siz[N],son[N],dep[N],top[N];

void dfs1(int x){

    dfn[x]=++cnt;siz[x]=1;son[x]=0;

    for(re i=head[x];i;i=nxt[i]){

        int y=to[i];

        if(y==fa[x])continue;

        fa[y]=x;dep[y]=dep[x]+1;

        dfs1(y);siz[x]+=siz[y];

        if(!son[x]||siz[y]>siz[son[x]])son[x]=y;

    }

}

void dfs2(int x,int f){

    top[x]=f;

    if(son[x])dfs2(son[x],f);

    for(re i=head[x];i;i=nxt[i]){

        int y=to[i];

        if(y==son[x]||y==fa[x])continue;

        dfs2(y,y);

    }

}

int LCA(int x,int y){

	//cout<<x<<" "<<y<<" "<<top[x]<<" "<<top[y]<<endl;

    while(top[x]!=top[y]){

        if(dep[top[x]]<dep[top[y]])swap(x,y);

        x=fa[top[x]];

    }

    return dep[x]<dep[y]?x:y;

}

所以就完事了

所以好像昂还有一个tarjan的离线算法

好像弱爆了，所以我基本不用他

巴特西

关于LCA的几点想法

倍增

$ code $

RMQ

$ code $

树链剖分

$ code $

最新文章

热门文章