一点小小的疑惑

P3261 [JLOI2015] 城池攻占

$dep_1$ 设为 $1$ 是因为可能最后会占领 $1$ 号点,设为 $0$ 就会少算 $1$ (样例会出现这种情况)。 至于 $dis_0$ 设为 $-1$ 是合并两个堆时如果只有两个点,它就可能出现点 $u$ 没有左儿子,但有右儿子的情况。而判断这个堆是否为空是判断根节点有没有左儿子,这样就会出错。
by xzc0920 @ 2023-11-01 17:46:53


@[ZhouZhiHeng](/user/251410)
by xzc0920 @ 2023-11-01 18:41:32


@[徐哲晨](/user/333576) thx
by ZhouZhiHeng @ 2023-11-02 11:56:29


@[xzc0920](/user/333576) 啊,突然意识到了,thks. 但是还有些不懂,如果 u 没有左儿子,只有右儿子,是不是说有些节点的堆 其实并不是左偏树
by Deamer @ 2024-03-30 18:23:56


@[Deamer](/user/585962) 不好意思,我的意思是右儿子的 dst 还是 0 没有改变,所以 dst[0] 要为 -1,但是右儿子理论上 dst 应为 1 ,所以说有些点的 dst 值是不对的?望解答
by Deamer @ 2024-03-30 18:27:10


艹,我懂了,左偏树在实现的时候叶子节点的 dst 是 0!
by Deamer @ 2024-03-30 18:28:16


|