重链剖分

重链剖分

优先走重儿子，路径跳不超过 \(O(\log n)\)

int siz[N],fa[N],dep[N],top[N],dfn[N],hson[N],dfc;//注意每个都要处理
void dfs1(int x,int Fa){
	fa[x]=Fa;
	siz[x]=1;
	hson[x]=0;
	for(int i=h[x];i;i=e[i].ne){
		int y=e[i].to;
		if(y==Fa)continue;
		dep[y] = dep[x]+1;
		dfs1(y,x);
		if(!hson[x]||siz[hson[x]]<siz[y])hson[x]=y;
		siz[x]+=siz[y];
	}
}
void dfs2(int x,int Fa,int topf){
	dfn[x]=++dfc;
	top[x]=topf;
	if(hson[x])dfs2(hson[x],x,topf);
	for(int i=h[x];i;i=e[i].ne){
		int y=e[i].to;
		if(y==Fa||y==hson[x])continue;
		dfs2(y,x,y);
	}
}
int lca(int x,int y){
	int X=x,Y=y;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	return y;
}