#P3244. [Noi2013]树的计数

    ID: 2429 传统题 1000ms 512MiB 尝试: 1395 已通过: 447 难度: 9 上传者: 标签>难度分类省选/NOI-组合数学双射计数排序与序列处理一维前缀和差分标记区间修改概率与期望指示变量期望线性性CF2600

[Noi2013]树的计数

[NOI2013] 树的计数

题目描述

对一棵有根树进行深度优先遍历(DFS)或广度优先遍历(BFS),分别得到它的 DFS 序和 BFS 序。不同的树可能同时具有相同的 DFS 序与 BFS 序。下图两棵树的 DFS 序均为 1,2,4,5,31,2,4,5,3,BFS 序均为 1,2,3,4,51,2,3,4,5。

具有相同 DFS 序和 BFS 序的两棵树

两种遍历中,同一父节点的孩子按相同的相对顺序访问。只有根节点的树高为 11。其他树的高度等于根的所有子树的最大高度加 11。

给定 DFS 序和 BFS 序。若共有 KK 棵不同的有根树符合要求,高度分别为 h1,h2,…,hKh_1,h_2,\ldots,h_K,求它们的平均高度。

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

输入格式

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

第二行是 11 到 nn 的一个排列,表示 DFS 序。第三行是 11 到 nn 的一个排列,表示 BFS 序。

保证至少存在一棵有根树符合这两个序列。

输出格式

输出一个实数,表示平均高度。四舍五入后保留恰好三位小数。

样例 1

5
1 2 4 5 3
1 2 3 4 5
3.500

样例 2

输入文件 · 输出文件

数据规模与约定

  • 对于 20%20\% 的数据,n≤10n\le 10。
  • 对于 40%40\% 的数据,n≤100n\le 100。
  • 对于 85%85\% 的数据,n≤2000n\le 2000。
  • 对于所有数据,2≤n≤2000002\le n\le 200000。

原赛按数值评分,输出与标准答案的绝对误差不超过 0.0010.001 时,该测试点得分。

原赛题面