luogu#P1232. [NOI2013] 树的计数

    ID: 5290 远端评测题 1000ms 125MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>递推2013NOI 系列广度优先搜索BFS深度优先搜索DFS

[NOI2013] 树的计数

题目描述

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

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

h1+h2++hKK\frac{h_1+h_2+\ldots+h_K}K

输入格式

第一行包含 11 个正整数 nn,表示树的节点个数。

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

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

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

输出格式

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

5 
1 2 4 5 3 
1 2 3 4 5

3.500

提示

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

数据范围

  • 对于 20%20\% 的测试数据,满足:n10n \le 10
  • 对于 40%40\% 的测试数据,满足:n100n \le 100
  • 对于 85%85\% 的测试数据,满足:n2×103n \le 2 \times 10^3
  • 对于 100%100\% 的测试数据,满足:2n2×1052 \le n \le 2 \times 10^5