‹ 上一题 下一题 ›

g7-07663. 树的中心 未做

1000 ms 256 MB 测试点 10 通过率 100% 自拟题GESP-77级·树的直径与重心阶梯·拔高

题目描述

给定一棵有 个节点的无根树,节点编号为 ,每条边的长度均为 。

对于树上的一个节点 ,定义它的偏心距为它到树上所有节点距离的最大值,记作

其中 表示 到 的唯一简单路径上的边数。

请你求出这棵树的中心:偏心距最小的节点。如果有多个节点的偏心距同时取到最小值,输出编号最小的那个。同时输出这个最小的偏心距。

输入格式

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

接下来 行,每行两个正整数 ,表示节点 与节点 之间有一条边。保证输入数据构成一棵树。

输出格式

一行两个整数,用一个空格隔开,依次表示树的中心编号和该节点的偏心距。

样例 1

输入:

5
1 3
3 5
5 2
5 4

输出:

3 2

说明:节点 到 、 的距离为 ,到 、 的距离为 ,偏心距为 ;节点 到 、 的距离为 ,到 的距离为 ,偏心距也为 。两者并列最小,取编号较小的 ,所以答案为 。

数据范围

  • 对于 的数据,;
  • 对于 的数据,;
  • 对于 的数据,,,输入保证是一棵树。

注意: 时树中只有一个节点,此时中心为 ,偏心距为 。

输入
输出

            
答案