自动搬运

查看原文

来自洛谷，原作者为

	Thomas_Cat 越学越菜。

搬运于2025-08-24 22:26:54，当前版本为作者最后更新于2020-12-19 21:58:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

赛后口胡题解：

Ps：可能受了验题影响因此可能代码像std就不放了（

对于该题，我们知道的条件是：

• 有一课二叉树，节点数为 $2^p-1$，其中 $x_i,x_{2i},x_{2i+1}$ 的关系很容易理解：父亲和左儿子右儿子。

• 从上面的到：在该二叉树中对于节点 $j$，可与 $2j,2j+1$交换位置，使其编号与值相等。

因此我们的处理方法如下：

• 找到 $x_i$

• 找到 $x_i,x_{x_i}$ 的 $LCA$

• 用儿子交换到 $x_{x_i}$

• 从 $x_q$ 处理至 $x_1$

口胡完毕（