Tree III
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

给出一棵有n个节点的节点标号为1~n的有根树(根为第一个节点,并给出从第2个节点到第n个节点的父结点),请你求解它的“第二直径”的长度,即树上任意两点距离非严格的第二长距离为多少(也就是说,如果存在两条不同的,长度均为max的路径,则返回max)。
树:一张有n个节点,n-1条边的无向连通图。
示例1

输入

复制
[1,2,3,4]

返回值

复制
3

说明

树构成了一条1-2-3-4-5的链,不难发现“第二直径”长度为3,其中1到4、2到5均满足要求。
示例2

输入

复制
[1,1,1,1]

返回值

复制
2

说明

树构成了一朵以1为中心的花,不难发现“第二直径”长度为2(当然此时的直径也为2)。

备注:

数据满足:
对于某些容易爆栈的语言,我们强烈建议你使用bfs而不是dfs