倍增LCA模板&ybt树上距离

用到的各个数组的意义
anc[i][j]表示从点i向根节点走(2^j)步到达的点的编号
dep[i]表示点i的深度
dis[i]表示点i到根节点之间的距离(i到根节点的简单路径上边的权值之和)

算法分析:

(1)题目给出了一颗无根树,因此我们建双向边,并任意选一个点作为根节点(我选择1)
(2)LCA的路径分解性质:
由于点x,y之间的路径(x——>y)可以分解成(x———>LCA(x,y))和
LCA(x,y)———>y两条路径。
因此x,y直接的距离为dis{x}+dis{y}-2*dis{LCA(x,y)}
(3)此时直接考虑求出LCA(x,y)

倍增求LCA:

(1)令dep{x}>dep{y},找到x的一个祖先,该祖先与y深度相等
(2)从该祖先和y出发,每次将两个点都向根节点走一步,直到找到在某一个位置,使得两点同时到达此位置,则此位置为LCA(x,y)
(3)一步一步向根节点走显然太慢,因此考虑用倍增加速该过程
最终复杂度O(nlogn+mlogn)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int n,m,anc[maxn][40],dep[maxn],dis[maxn],indu[maxn];
int head[maxn],ecnt=-1;
struct mint
{
	int nxt,v,w;
}e[maxn<<1];
void addline(int u,int v,int w)
{
	e[++ecnt].nxt=head[u];
	e[ecnt].v=v;
	e[ecnt].w=w;
	head[u]=ecnt;
}	
void dfs(int x,int fa,int w)
{
	dep[x]=dep[fa]+1;
	anc[x][0]=fa;
	dis[x]=dis[fa]+w;
	for(int i=1;i<=20;++i) anc[x][i]=anc[anc[x][i-1]][i-1];
	for(int i=head[x];~i;i=e[i].nxt) 
	{
		if(e[i].v!=fa) dfs(e[i].v,x,e[i].w);
	}
	return;	
}//预处理出dis,anc,dep数组
int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;--i)
	{
		if(dep[anc[x][i]]>=dep[y]) x=anc[x][i];
	}//调整两点深度,是两点深度相等
	if(x==y) return x;//若深度相等时两点重合,则y为x的祖先,二者LCA为y(此时x也在y的位置上)
	for(int i=20;i>=0;--i)
	{
		if(anc[x][i]!=anc[y][i]) 
		{
			x=anc[x][i];
			y=anc[y][i];
		}
	}	//每次向上走相同距离
	return anc[x][0];
}
int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;++i)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		addline(a,b,c);
		addline(b,a,c);
	}
	dfs(1,1,0);
	int x,y;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		int fa=LCA(x,y);
		int ans=dis[x]+dis[y]-2*dis[fa];
		printf("%d\n",ans); 
	}
	return 0; 
}

tips:

就这水题我debug还用了30min
(1)head记得赋初值
(2)如果在树上建了双向边,那么遍历其子节点时,一定要写成
if(e[i].v!=fa[x]) dfs(e[i].v,x),避免回到x的父节点。
否则会一直递归下去,直到爆栈。特征就是MLE(其实是RE,但是爆栈了所以也是爆空间)
(3)手动输出式的断点找bug是真的好用

倍增LCA模板&ybt树上距离

上一篇:ArrayList源码+扩容机制分析


下一篇:为什么产生大数据技术?