#2665. 「NOI2013」树的计数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

我们知道一棵有根树可以进行深度优先遍历(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

见附加文件中的 count.incount.ans.

数据范围与提示

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

对于 20\% 的测试数据,满足: n \le 10

对于 40\% 的测试数据,满足: n \le 100

对于 85\% 的测试数据,满足: n \le 2000

对于 100\% 的测试数据,满足: 2 \le n \le 200\ 000