申请添加题解(不同于任何题解的新做法)
查看原帖
申请添加题解(不同于任何题解的新做法)
551861
strcmp楼主2024/12/24 18:57

https://www.luogu.com.cn/article/vlz0pqc5

rt,基于 dfs 序排行 n2\lceil \frac{n}{2} \rceil 的那个点祖先链中必定包含重心的做法。

知道了这个结论,那么这个做法的思维量就远低于其它题解,而且可扩展性也比其它题解都强。比如这东西完全可以做一次删去 kk 个子树求重心的问题。

2024/12/24 18:57
加载中...