M_sea的博客

M_sea的博客

A Mengbier

题解 CF1129E 【Legendary Tree】

posted on 2019-04-25 08:18:03 | under 题解 |

神仙题。

钦定 $1$ 为根节点,那么可以通过 $n-1$ 次询问得到每个点的子树的 $size$ 。

具体方法是,对于第 $i$ 个点询问 $(\{1\},\big\{U-\{1\}-\{i\}\big\},i)$ ,返回的值就是 $size[i]$ 。

把 $[2,n]$ 按 $size$ 从小到大排序,这样子 $i$ 的儿子一定在 $i$ 左边。

我们把所有的没有确定父亲的点存在一个 $\mathrm{set}$ 里面。

从左往右处理这个序列。首先如果当前点有儿子,就找;然后把它加到 $\mathrm{set}$ 里面。

找儿子的过程是这样的:首先把当前的 $\mathrm{set}$ 分成两半,如果左边有子节点就往左边走,右边一样处理。

这样子可以找到儿子。把儿子的父亲记下来,然后从 $\mathrm{set}$ 中删去即可。

询问次数最多的点在 $6000$ 次左右。

建议画图理解。具体实现及细节见代码