[NOI2013] 树的计数

题目描述

我们知道一棵有根树可以进行深度优先遍历(DFS)以及广度优先遍历(BFS)来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同,并且它们的 BFS 序也有可能相同,例如下面两棵树的 DFS 序都是 `1 2 4 5 3`,BFS 序都是 `1 2 3 4 5`。 ![](https://cdn.luogu.com.cn/upload/pic/183.png) 现给定一个 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

说明

如果输出文件的答案与标准输出的差不超过 $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$。