警示后人
查看原帖
警示后人
710556
weiguoliang楼主2024/11/24 22:35

如果你的代码的求LCA是这样写的:

pll lca(ll x,ll y){ll i,mx=-inf;
	if(dep[x]<dep[y])swap(x,y);
	for(i=17;i>=0;i--){
		if(dep[fa[x][i]]>=dep[y]){
			x=fa[x][i];
			mx=max(ma[x][i],mx);
		}
	}
	if(x==y)return mp(x,mx);
	for(i=17;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i],y=fa[y][i];
			mx=max({ma[x][i],ma[y][i],mx});
		}
	}
	return mp(fa[x][0],max({mx,g[x],g[y]}));
}

请注意,这样是错的,因为先将xxyy点跳上去了,求的maxmax就不对了,应当将求maxmax放到x=fa[x][i]x=fa[x][i]

2024/11/24 22:35
加载中...