#P3244. [Noi2013]树的计数
[Noi2013]树的计数
[NOI2013] 树的计数
题目描述
对一棵有根树进行深度优先遍历(DFS)或广度优先遍历(BFS),分别得到它的 DFS 序和 BFS 序。不同的树可能同时具有相同的 DFS 序与 BFS 序。下图两棵树的 DFS 序均为 ,BFS 序均为 。

两种遍历中,同一父节点的孩子按相同的相对顺序访问。只有根节点的树高为 。其他树的高度等于根的所有子树的最大高度加 。
给定 DFS 序和 BFS 序。若共有 棵不同的有根树符合要求,高度分别为 ,求它们的平均高度。
输入格式
第一行包含一个正整数 ,表示节点数。
第二行是 到 的一个排列,表示 DFS 序。第三行是 到 的一个排列,表示 BFS 序。
保证至少存在一棵有根树符合这两个序列。
输出格式
输出一个实数,表示平均高度。四舍五入后保留恰好三位小数。
样例 1
5
1 2 4 5 3
1 2 3 4 5
3.500
样例 2
数据规模与约定
- 对于 的数据,。
- 对于 的数据,。
- 对于 的数据,。
- 对于所有数据,。
原赛按数值评分,输出与标准答案的绝对误差不超过 时,该测试点得分。