这题几个星期前看了一下午题解没看懂，现在看了一会就看懂了。可能是我太蠢了。

题目链接
题意：给一棵树的dfs序和bfs序，求树高的期望，保留3位小数。($n \le 200000$)

先把节点重标号，把bfs序为$i$的节点标号为$i$。
设$a_i$为$i$的dfs序，$b_i$为dfs序为$i$的节点(即$a_{b_i} = i$)， $i$的深度为$d_i$，那么一种划分方案合法当且仅当：

  • $d_1 = 1, d_2 = 2$。
  • $d_i \le d_{i + 1} \le d_i + 1$。
  • 如果$a_i > a_{i + 1}$，那么$d_{i+1} = d_i + 1$。
  • 如果$b_i < b_{i + 1}$，那么$d_{b_{i + 1}} - d_{b_i} \le 1$

上述条件的必要性显然，对于充分性的证明，可以给出一种构造：
按dfs序枚举所有节点，维护一个栈表示从1号点到当前点的路径上所有节点，那么当新加入一个点的时候：

  • 如果栈顶节点的深度$+1=$当前节点深度，那么把当前节点置为栈顶节点最靠右的孩子，并把当前节点插入栈中。
  • 否则一定有当前节点的深度$\le$栈顶节点的深度，不断从栈中弹出节点，直到满足上一条的条件，进行上一条的操作即可。

对于这个构造的正确性：

  • 每个节点的深度是正确的。
  • 对于深度相同的一段，根据上述条件，它们的dfs序一定是递增的。那么，对于深度相同的节点，它们的相对顺序没有改变。

那么构造的正确性得到了证明，上述条件的充要性得证了。同时，根据构造过程，可以发现一种合法的$d$一定恰好对应着一种方案，那么就是要求所有合法的$d$的$d_n$的期望。
一种合法的$d$可以对应成一个集合$S = \lbrace i | 1 \le i < n, d_i + 1 = d_{i + 1} \rbrace$，深度就是$|S| + 1$。
如果一个$S$合法，根据上述条件，也有一些限制：

  • 根据第一、三个条件，需要满足$S$中一定要有$1$和某些特定元素，这些元素对答案的贡献是$1$。

  • 根据第四个条件，对于$2 \le i < n$，如果$b_i < b_{i+1}$，需要满足$[b_i, b_{i + 1} )$中只有不超过一个元素在$S$中。那么也就是说：

    • 如果$b_i + 1 < b_{i + 1}$，那么$b_i$和$b_{i + 1}$之间一定有一个因满足第三个条件而一定在$S$内的元素，那么$[b_i, b_{i + 1})$中不能有除了该元素之外的其它元素在$S$中。
    • 否则有$b_i + 1 = b_{i + 1}$，如果$b_i$不是因为上一条的影响而不能在$S$中，那么$b_i$是否在$S$中可以任意选择，且不影响其它元素的选择。那么它对答案的贡献就是$0.5$。

根据上述方法计算答案即可。
复杂度$O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
int n, a[maxn + 10], b[maxn + 10], c[maxn + 10], d[maxn + 10];
double ans = 2;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int x; scanf("%d", &x);
		a[x] = i;
	}
	for (int i = 1; i <= n; ++i) {
		int x; scanf("%d", &x);
		b[i] = a[x]; c[b[i]] = i;
	}
	for (int i = 2; i < n; ++i)
		if (c[i] + 1 < c[i + 1]) {
			++d[c[i]]; --d[c[i + 1]];
		}
	for (int i = 2; i < n; ++i) {
		d[i] += d[i - 1];
		if (b[i] > b[i + 1]) ++ans;
		else if (!d[i]) ans += 0.5;
	}
	printf("%.3lf", ans);
}