自动搬运

查看原文

来自洛谷，原作者为

	一只绝帆 就让我在风儿中独舞，唱着只有云儿能听懂的哀歌。

搬运于2025-08-24 21:22:43，当前版本为作者最后更新于2024-04-25 15:16:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P1232 [NOI2013] 树的计数

定义 $\rm dfs$ 是每个点按照儿子顺序依次递归，$\rm bfs$ 是取出队首将队首的儿子加入队列。

（两种搜索的”儿子顺序“这个量已经确定。）

给定 $\rm dfs$ 序和 $\rm bfs$ 序，求出满足二者的所有树的高度的平均数。

保证存在一棵树满足条件。

$n\le 2\times 10^5$。

首先把平均数变成所有合法树中随一个，期望高度。

高度其实就是将 $\rm bfs$ 序分成若干段作为若干层，段数就是高度，所以就是期望分段次数 $+1$。

期望线性性拆成每个点后面分段的概率和。

先把点们重新标号，按照 $\rm bfs$ 序变为 $1\sim n$，$\rm dfs$ 序相应变化，令 $d_i$ 表示点 $i$ 什么时候被 $\rm dfs$ 到（$\rm dfs$ 序的逆排列）。

考虑 $i$ 与 $i+1$：

• 若 $d_i+1=d_{i+1}$，则 $i+1$ 可以是 $i$ 的儿子或兄弟（此时 $i$ 为叶子），没有什么限制。
• 若 $d_i+1<d_{i+1}$，则 $i+1$ 必定是 $i$ 的兄弟，因为 $\rm bfs$ 完可以立即到达但 $\rm dfs$ 去找别人了，该间隔被分段的概率是 $0$。
• 若 $d_{i}+1>d_{i+1}$，则 $i+1$ 必定与 $i$ 分层，因为 $\rm dfs$ 先走到 $i+1$ 再走到 $i$，因为儿子顺序固定所以二者不可能同层，该间隔被分段的概率是 $1$。

想象一棵树每个点的儿子都已经按照儿子顺序从左到右排好了，那么第三种情况就是走到一层的结尾，跑到了下一层的开头，只要 $x$ 所在层的前面有其他的非叶子节点，那就会导致该点的儿子先被 $\rm dfs$ 到。

而第一种情况说的是所有爷爷——父亲——独生儿子的情况 与 所有 父亲（原爷爷）——儿子 1（作为叶子，原父亲）——儿子 2（原独生儿子，不一定是叶子）的情况是对偶的，即树上所有的这两种结构可以相互转化，而不影响其他任何结构以及 $\rm dfs,bfs$ 序。

（注意后种情况仍需保证原爷爷的其他儿子顺序不变，仅仅是把原父亲这个位置换成了先”原父亲“再”原独生儿子“这个结构。）

继续发掘，你发现两序确定后唯一符合两序的调整就是该调整，进一步地讲：将这些结构全部调整为第一种形式，那考虑所有最高链上的该结构每个结构可以自由选择是否调整为第二种形式让高度减小 $1$，所以每个”不确定是否分段“的间隔实质上产生了 $0.5$ 的贡献，即两种情况各占所有合法情况的一半。

此时我们确定了一些概率，考虑接着找找条件，考虑 $x={\rm dfs}_i$ 与 $y={\rm dfs}_{i+1}$：

• 若 $x+1>y$，说明 $x>y$，也就是说情况必然为 $x$ 是某个叶子，递归完 $x$ 到了 $y$，不能得到什么有用结论。
• 若 $x+1=y$，这种就是上面的 $d_i+1=d_{i+1}$，同样考虑过了。
• 若 $x+1<y$，由于二者之间是先后递归的关系，且回溯的情况被上两种统计到了，所以 $y$ 是 $x$ 的一个儿子，二者深度相差不超过 $1$，这说明 $[x,y-1]$ 中有且仅有一个元素后面可以放分段。

不难发现上文中 $d_i+1>d_{i+1}$ 的情况一定发生在符合第三种情况的这段区间中间，其实就是因为 $x$ 这个节点有同层的、更靠后的节点还没有 $\rm bfs$ 到，所以 $\rm bfs$ 的过程需要过一会儿才到下一层。

既然这个”有且仅有一个元素“已经确定是哪个元素了，不妨我们视作将 $[x,y-1]$ 这段区间禁止起来，全部不能产生贡献，而在上文产生 $1$ 的贡献时直接加到答案中。

题解中有人不会证充要（似乎所有人都没证），为什么这样可以 $\rm ban$ 掉所有不可能分段的点？

其实你可以参考上图，本层 （下称第 $d$ 层）的每个节点都与它的第一个儿子产生了这样的 $\rm banpair$，这首先保证了 $d+1$ 层除了（第 $d$ 层最后一个节点的儿子）的所有点后面不能分层。

那第 $d+1$ 层的最后那些点怎么限制？其实仔细思索一下你发现它们不应限制，如果它们中的一个节点没有儿子（且不是已经判断过的必须分割点且没有被 $\rm ban$），那说明它符合上文提到过的可调整结构，所以它是应当贡献 $0.5$ 的。

而如果它有儿子，你惊喜地发现它符合上图中 $x$ 的地位，它实质上得到了应有的限制。