最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

int dep[maxn],fa[maxn][64]; 
//dep统计深度，fa[i][j]向上跳j步的位置，倍增着跳                 
void dfs(int u,int father){
	dep[u]=dep[father]+1;
	for (int i=1;i<64;i++){
		//原理结合上图理解 
		fa[u][i]=fa[fa[u][i-1]][i-1];
	} 
	
	
	for (int v=head[u];~v;v=edge[v].next){
		if (edge[v].v!=father){
			dfs (edge[v].v,u);
		}
	} 
	
} 

int lca(int u,int v){
	
	if (dep[u]<dep[v]){
		//使得u的深度更深 
		swap(u,v);
	}
	for (int i=63;i>=0;i--){
		//跳到同一层 
		//如果 u跳到第i步的祖先节点的深度仍然比v的深度大，则u继续向上跳
		//如果深度比较小，证明跳的太远，不操作，下次近一些
		//直到跳到同意深度 
		if (dep[fa[u][i]]>=dep[v]){
			u=fa[u][i];
		}
	}
	
	if(u==v){
		//如果相等则最近公共祖先找到了 
		return v;
	} 
	
	for (int i=62;i>=0;i--){
		//一起向上跳相同远，如果位置相同，则找到公共祖先
		//但不见得是最近公共祖先 ，那就跳近点试试
		//如果不相等，那最近公共祖先一定还在上面接着跳。 
		//直到跳到最新公共祖先的子节点上 
		if (fa[u][i]!=fa[v][i]){
			u=fa[u][i],v=fa[v][i];
		}	
	}
	//此时u的父节点就是最近公共祖先 
	return fa[u][0];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

vector <pair<int,int>> query[maxn];
//query[a]<paor<b,t>>表示第t次询问，询问a，b的最近公共祖先
int fa[maxn],ans[maxn];
bool vis[maxn];

int find (int u){
	int a=u;
	while (a!=fa[a]){
		a=fa[a];
	}
	
	while (a!=fa[u]){
		int t=fa[u];
		fa[u]=a;
		u=t;
	}
	return a;
}

void tarjan(int u){
//注意询问要双向存储
	vis[u]=true;
	for (int v=head[u];~v;v=edge[v].next){
	//用递归自下向上使用并查集维护他们的公共祖先，当a，b第一次
	//都出现在并查集上时，就找到了他们的最近公共祖先
		if (!vis[edge[v].v]){
			tarjan(edge[v].v);
			fa[edge[v].v]=u;
		}
	}
	
	for (auto q : query[u]){
		int v=q.first,i=q.second;
		if (vis[v]){
		//因为不知道a,b谁后进入并查集，所以询问要双向存储。
			ans[i]=find[v];
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

int fa[maxn],dep[maxn],son[maxn],sz[maxn];
int top[maxn];
void dfs1(int u,int father)//搞 fa,dep,son,即父节点，深度，重儿子 
{
	fa[u]=father;
	dep[u]=dep[father]+1;
	sz[u]=1;
	for (int v=head[u];~v;v=edge[v].next){
		if (edge[v].v!=father){
			dfs1(edge[v].v,u);
			sz[u]+=sz[edge[v].v];
			if (sz[son[u]]<sz[edge[v].v]){
				son[u]=edge[v].v;
			}
		}
	}
}

void dfs2(int u,int t){//搞 top 即重链的头 
	top[u]=t;
	if (!son[u]){
		return ;
		//无重儿子返回 
	}
	dfs2(son[u],t);
	for (int v=head[u];~v;v=edge[v].v){
		if (edge[v].v==fa[u]||edge[v].v==son[u]){
			contime ;
		}
		dfs(edge[v].v,edge[v].v);
	} 
}
int lca(int u,int v){
	while (top[u]!=top[v]){
		//不在一条重链上，则链头深的向上跳， 
		if (dep[top[u]]<dep[top[v]]) {
			swap(u,v);
		}
		//跳到另一条重链上，即链头的父节点 
		u=fa[top[u]];
	}
	//若在同一条重链上，则深度更浅的就是最近公共祖先 
	return dep[u]<dep[v]?u:v;
}