树链剖分LCA求调
  • 板块灌水区
  • 楼主Martlet
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/5/27 19:27
  • 上次更新2023/10/23 14:34:03
查看原帖
树链剖分LCA求调
543717
Martlet楼主2023/5/27 19:27

dfs2死循环了

#include<bits/stdc++.h>
using namespace std;
const int N = 200000+10;
vector<int> G[N] ;
int dep[N],fa[N],hson[N],sz[N],top[N],dfn[N];
void dfs1(int u,int p){//u当前访问到的,p父节点。 
	fa[u] = p;
	sz[u] = 1;
	dep[u] = dep[p]+1;
	int maxh = 0;
	for(int i = 0;i < G[u].size();i++){
		int v = G[u][i];
		if(v == p)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(maxh < sz[v]){
			hson[u] = v;
			maxh = sz[v];
		}
	} 
	if(sz[u] == 1)hson[u] == -1;
	
}
int cnt;//记录是第几次访问 
void dfs2(int u,int p){
    //先遍历重儿子 
    cnt++;
	dfn[u] = cnt; 
	if(hson[u] == -1)return;
	top[hson[u]] = top[u];
    dfs2(hson[u],u); 
   
	for(int i = 0;i < G[u].size();i++){
		int v = G[u][i];
		if(v == p || hson[u] == v)continue;
		
		top[v] = v;
		
		
	    dfs2(v,u);
	} 
}
int lca(int u,int v){
	if(top[u] == top[v])return dep[u]<dep[v] ? u : v;//那个深度小就取哪个。
	if(dep[top[u]]<dep[top[v]]) return lca(u,fa[top[v]]);
	else return lca(fa[top[u]],v);
	//因为他是要跳到top的父亲上所以要比较两个top的深度; 
}
int main(){
    int  n;
	cin>>n;
	for(int i = 1;i <= n-1;i++){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	} 
	dfs1(1,1);
	dfs2(1,1);
	int q;
	cin>>q;
	while(q--){
		int u,v;
		cin>>u>>v;
		cout<<lca(u,v)<<endl;
	}
	return 0;
}
2023/5/27 19:27
加载中...