3839. [NOI 2013] 树的计数

【题目描述】

我们知道一棵有根树可以进行深度优先遍历（$DFS$）以及广度优先遍历（$BFS$）来生成这棵树的 $DFS$ 序以及 $BFS$ 序。两棵不同的树的 $DFS$ 序有可能相同，并且它们的 $BFS$ 序也有可能相同，例如下面两棵树的 $DFS$ 序都是 $1$ $2$ $4$ $5$ $3$，$BFS$ 序都是 $1$ $2$ $3$ $4$ $5$。

现给定一个 $DFS$ 序和 $BFS$ 序，我们想要知道，符合条件的有根树中，树的高度的平均值。即，假如共有 $K$ 棵不同的有根树具有这组 $DFS$ 序和 $BFS$ 序，且他们的高度分别是 $h_1, h_2, \ldots, h_K$，那么请你输出：$\frac{h_1+h_2+\ldots+h_K}K$

【输入格式】

第一行包含 $1$ 个正整数 $n$，表示树的节点个数。

第二行包含 $n$ 个正整数，是一个 $1 \ldots n$ 的排列，表示树的 $DFS$ 序。

第三行包含 $n$ 个正整数，是一个 $1 \ldots n$ 的排列，表示树的 $BFS$ 序。

输入保证至少存在一棵树符合给定的两个序列。

【输出格式】

输出 $1$ 个实数，四舍五入保留恰好三位小数，表示树高的平均值。

【样例1输入】

5 
1 2 4 5 3 
1 2 3 4 5

【样例1输出】

3.500

【样例2/3】

点击下载样例2/3

【数据规模与约定】

如果输出文件的答案与标准输出的差不超过 $0.001$，则将获得该测试点上的分数，否则不得分。

对于 $20\%$ 的测试数据，满足：$n \le 10$；

对于 $40\%$ 的测试数据，满足：$n \le 100$；

对于 $85\%$ 的测试数据，满足：$n \le 2 \times 10^3$；

对于 $100\%$ 的测试数据，满足：$2 \le n \le 2 \times 10^5$。