• 周六. 8月 20th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[APIO2020]有趣的旅途

admin

11月 28, 2021

注意到第一个点是可以钦定的。
那么我们考虑在重心的子树里反复横跳。
每次选择不同子树里的深度最大的点。
在同一颗子树里可能会在lca处出现问题。
那么我们选择重心,要考虑到会不会出现一颗子树不够选的操作。
依照旭爷的证明,在一个时刻一定会出现:
大的那颗子树的大小等同于另外两颗的子树和。
这样我们只要按两颗子树的操作选即可。

然后我们要考虑一些操作:

找到重心:询问在0下的子树大小,选择(n-siz leq lfloor frac{n}{2} floor)(siz)最小当做重心,这个显然(n)
找到深度,这个显然(n)次。
找到自己在哪颗子树,那么我们考虑按子树大小降序考虑,依照(dep)和距离考虑,找到了就(dep),那么这样是(a * 1 + b * 2 + c * 3 leq 2*n)

所以可以卡过。

发表回复

您的电子邮箱地址不会被公开。