路径更新和查询的时候,跳链顶是选择链顶深度更大的跳,为什么不直接选择当前节点深度更大的跳?
实测后者会 WA,求解释原因。
void pathadd(int x, int y, int z)
{
while (top[x] != top[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);
}