比赛场次 559
比赛名称 4043级2023省选练习赛1
比赛状态 已结束比赛成绩
开始时间 2023-03-03 18:30:00
结束时间 2023-03-03 22:00:00
开放分组 全部用户
注释介绍 今日事,今日毕
题目名称 树的计数
输入输出 treecount.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 20 评测插件
用户 结果 时间 内存 得分

树的计数

★★★☆   输入文件:treecount.in   输出文件:treecount.out   评测插件
时间限制:1 s   内存限制:256 MiB

【题目描述】

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

点击下载样例2/3

【数据规模与约定】

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

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

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

对于 $85\%$ 的测试数据,满足:$n \le 2 \times 10^3$;

对于 $100\%$ 的测试数据,满足:$2 \le n \le 2 \times 10^5$。