求助LCA
  • 板块学术版
  • 楼主conprour
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/10/11 16:21
  • 上次更新2023/11/4 04:04:33
查看原帖
求助LCA
234783
conprour楼主2021/10/11 16:21

RT,求帮忙看看下面这个LCA板子有没有问题。感激不尽!

void dfs(int u,int fa)
{
	for(int i=1;i<=19;i++) f[i][u]=f[i-1][f[i-1][u]];
	for(int i=head[u];~i;i=a[i].nxt)
	{
		int v=a[i].to;
		if(v==fa) continue;
		dis[v]=dis[u]+a[i].w;
		dep[v]=dep[u]+1;
		f[0][v]=u;
		dfs(v,u);
	}
}
inline int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--)
	 	if(dep[f[i][x]]<=dep[y]&&f[i][x]) x=f[i][x];
	if(x==y) return x;
	for(int i=19;i>=0;i--)
		if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
	return f[0][x];
}
inline ll Dis(int x,int y){return dis[x]+dis[y]-(dis[lca(x,y)]<<1);}
2021/10/11 16:21
加载中...