P3884 [JLOI2009]二叉树问题

    • 938通过
    • 2.4K提交
  • 题目提供者 Hoshizawa
  • 评测方式 云端评测
  • 标签 搜索 最近公共祖先,LCA 树上距离 树链剖分,树剖 深度优先搜索,DFS 各省省选 2009 吉林 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 512MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    如下图所示的一棵二叉树的深度、宽度及结点间距离分别为:

    深度:4 宽度:4(同一层最多结点个数)

    结点间距离: ⑧→⑥为8 (3×2+2=8)

    ⑥→⑦为3 (1×2+1=3)

    注:结点间距离的定义:由结点向根方向(上行方向)时的边数×2,

    与由根向叶结点方向(下行方向)时的边数之和。

    输入输出格式

    输入格式:

    输入文件第一行为一个整数n(1≤n≤100),表示二叉树结点个数。接下来的n-1行,表示从结点x到结点y(约定根结点为1),最后一行两个整数u、v,表示求从结点u到结点v的距离。

    输出格式:

    三个数,每个数占一行,依次表示给定二叉树的深度、宽度及结点u到结点v间距离。

    输入输出样例

    输入样例#1: 复制
    10                                
    1 2                            
    1 3                            
    2 4
    2 5
    3 6
    3 7
    5 8
    5 9
    6 10
    8 6
    
    输出样例#1: 复制
    4
    4
    8
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。