P1232 [NOI2013]树的计数

    • 342通过
    • 703提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 广度优先搜索,BFS 深度优先搜索,DFS 递推 NOI系列 2013
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    能评测了哦。

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

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

    (h1+h2..+hk)/k

    输入输出格式

    输入格式:

    输入文件count.in共有3行。

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

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

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

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

    输出格式:

    输出文件count.out仅包含1个实数,四舍五入保留恰好三位小数,表示树高的平均值。

    输入输出样例

    输入样例#1: 复制
    5 
    1 2 4 5 3 
    1 2 3 4 5
    
    输出样例#1: 复制
    3.500
    

    说明

    【评分方式】

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

    【数据规模和约定】

    20%的测试数据,满足:n≤10;

    40%的测试数据,满足:n≤100;

    85%的测试数据,满足:n≤2000;

    100%的测试数据,满足:2≤n≤200000。

    【说明】

    树的高度:一棵有根树如果只包含一个根节点,那么它的高度为1。否则,它的高度为根节点的所有子树的高度的最大值加1。

    对于树中任意的三个节点a , b , c ,如果a, b都是c的儿子,则a, b在BFS序中和DFS序中的相对前后位置是一致的,即要么a都在b的前方,要么a都在b的后方。

    【时间限制】

    1s 【空间限制】

    256000KB

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。