luogu#P1232. [NOI2013] 树的计数
[NOI2013] 树的计数
题目描述
我们知道一棵有根树可以进行深度优先遍历(DFS)以及广度优先遍历(BFS)来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同,并且它们的 BFS 序也有可能相同,例如下面两棵树的 DFS 序都是 1 2 4 5 3
,BFS 序都是 1 2 3 4 5
。
现给定一个 DFS 序和 BFS 序,我们想要知道,符合条件的有根树中,树的高度的平均值。即,假如共有 棵不同的有根树具有这组 DFS 序和 BFS 序,且他们的高度分别是 ,那么请你输出:
输入格式
第一行包含 个正整数 ,表示树的节点个数。
第二行包含 个正整数,是一个 的排列,表示树的 DFS 序。
第三行包含 个正整数,是一个 的排列,表示树的 BFS 序。
输入保证至少存在一棵树符合给定的两个序列。
输出格式
输出 个实数,四舍五入保留恰好三位小数,表示树高的平均值。
5
1 2 4 5 3
1 2 3 4 5
3.500
提示
如果输出文件的答案与标准输出的差不超过 ,则将获得该测试点上的分数,否则不得分。
数据范围
- 对于 的测试数据,满足:;
- 对于 的测试数据,满足:;
- 对于 的测试数据,满足:;
- 对于 的测试数据,满足:。