LAC 算法总结

To begin with，what is 'LAC'

就是说，在一棵树中，照亮个节点的最近路线

先来一个模板题

题目描述

给定一棵n个点的树，Q个询问，每次询问点x到点y两点之间的距离。

输入格式：

第一行一个正整数n，表示这棵树有n个节点；

接下来n−1行，每行两个整数x，y，表示 x，y之间有一条连边； 然后一个整数Q，表示有Q个询问；

接下来Q行，每行两个整数x，y表示询问x到y的距离。

输出格式：

输出Q行，每行表示每个询问的答案。

假如用最短路径算法大家都清楚，慢得~~

再补充一个数据范围

1≤n,m,Q≤10^5 ；1≤x,y≤n。

就更不行了

所以，我们需要一个更有效的算法

两个点的距离无非就是

这两个点的深度和减去他们的公共祖先的深度*2

interesting...

不妨看看代码

#include<bits/stdc++.h>
using namespace std;
#define N 1000009
int n,q,nxt[N*2],to[N*2],first[N*2],tot=0;
int f[N][21],dep[N];//f[i][j]表示第i各节点2^j次方的祖先 dep表示节点深度
int q;
void add(int u,int v)//创建邻接表
{
	nxt[++tot]=first[u];first[u]=tot;to[tot]=v;
	nxt[++tot]=first[v];first[v]=tot;to[tot]=u;
}
void init(int u,int father)
{
	dep[u]=dep[father]+1;
	for(int i=0;i<=19;i++)
	{
		f[u][i+1]=f[f[u][i]][i];//标记祖先
	}
	for(int e=first[u];e;e=nxt[e])//穷举每个儿子节点
	{
		int v=to[e];
		if(v==father) continue;
		f[v][0]=u;
		init(v,u);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return x;
	}//将x,y跳到同一高度
	for(int i=20;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}//两个（人）一起跳 真浪漫~~
	}
	return f[x][0];
}
int dist(int x,int y)
{
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int main()
{
	freopen("dis.in","r",stdin);
	//freopen("dis.out","w",stdout);
	scanf("%d",&n);
	int xx,yy;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&xx,&yy);
		add(xx,yy);
	}
	init(1,0);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&xx,&yy);
		printf("%d\n",dist(xx,yy));
	}
	
	return 0;
}

当然，有些部分（如邻接表），大家应当有自己熟悉的码风，只看关键的。