关于树剖的小问题
查看原帖
关于树剖的小问题
781046
tai_chi楼主2023/8/28 10:24

路径更新和查询的时候,跳链顶是选择链顶深度更大的跳,为什么不直接选择当前节点深度更大的跳?

实测后者会 WA,求解释原因。

void pathadd(int x, int y, int z)
{
	while (top[x] != top[y])
	{
		// if (dep[x] < dep[y]) 是错的
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);
		add(1, dfn[top[x]], dfn[x], z);
		x = fa[top[x]];
	}
	if (dfn[x] > dfn[y])
		swap(x, y);
	add(1, dfn[x], dfn[y], z);
}
2023/8/28 10:24
加载中...