警示:关于k的下界
查看原帖
警示:关于k的下界
555833
haozexu楼主2024/5/24 11:39

内层 k 应该满足条件 j−k≤siz[x]−siz[v]j-k\le \mathbf{siz}[x]-\mathbf{siz}[v]
移项得到 k≥j−(siz[x]−siz[v])k\ge j-(\mathbf{siz}[x]-\mathbf{siz}[v])

这是为了防止之前的其他子树选不出这么多黑点,这就是为什么有的题解初值赋 −1-1 ,但是那样时间好像不对?我不会证。

2024/5/24 11:39
加载中...