最小生成树、倍增16分可能得错误
查看原帖
最小生成树、倍增16分可能得错误
413301
Digital_Sunrise楼主2025/8/29 16:56

lca中:

int lca(int u,int v)
{
	int ans = 0;
	if(dep[u] > dep[v]) swap(u,v);//dep[u] < dep[v],u更靠近根节点
	while(dep[u] != dep[v])
	{
		ans = max(ans,mx[v][lg2[dep[v] - dep[u]]]);
		v = fa[v][lg2[dep[v] - dep[u]]];
	}
	if(u == v) return ans;
	for(int i = lg2[dep[u]];i >= 0;i--)
	{
		if(fa[u][i] != fa[v][i])
		{
			ans = max(ans,mx[u][i]);
			ans = max(ans,mx[v][i]);
			u = fa[u][i],v = fa[v][i];
			
		}
	}
	ans = max(ans,mx[u][0]);
	return max(ans, mx[v][0]);
}

在最后一步跳到父节点时可能只考虑了ans = max(ans,mx[u][0]); 而没有考虑另一点跳的边权。

2025/8/29 16:56
加载中...