给定一个公司的网络,由 nn 台交换机和 mm 台终端电脑组成,交换机与交换机、交换机与电脑之间使用网络连接。
交换机按层级设置,编号为 11 的交换机为根交换机,层级为 11。
其他的交换机都连接到一台比自己上一层的交换机上,其层级为对应交换机的层级加 11。
所有的终端电脑都直接连接到交换机上。
当信息在电脑、交换机之间传递时,每一步只能通过自己传递到自己所连接的另一台电脑或交换机。
请问,电脑与电脑之间传递消息、或者电脑与交换机之间传递消息、或者交换机与交换机之间传递消息最多需要多少步。
输入格式
输入的第一行包含两个整数 n,mn,m,分别表示交换机的台数和终端电脑的台数。
第二行包含 n−1n−1 个整数,分别表示第 2、3、……、n2、3、……、n 台交换机所连接的比自己上一层的交换机的编号。第 ii 台交换机所连接的上一层的交换机编号一定比自己的编号小。
第三行包含 mm 个整数,分别表示第 1、2、……、m1、2、……、m 台终端电脑所连接的交换机的编号。
输出格式
输出一个整数,表示消息传递最多需要的步数。
数据范围
前 30%30% 的评测用例满足:n≤5,m≤5n≤5,m≤5。
前 50%50% 的评测用例满足:n≤20,m≤20n≤20,m≤20。
前 70%70% 的评测用例满足:n≤100,m≤100n≤100,m≤100。
所有评测用例都满足:1≤n≤10000,1≤m≤100001≤n≤10000,1≤m≤10000。
输入样例1:
4 2
1 1 3
2 1
输出样例1:
4
样例1解释
样例的网络连接模式如下,其中圆圈表示交换机,方框表示电脑:
其中电脑 11 与交换机 44 之间的消息传递花费的时间最长,为 44 个单位时间。
输入样例2:
4 4
1 2 2
3 4 4 4
输出样例2:
4
样例2解释
样例的网络连接模式如下:
其中电脑 11 与电脑 44 之间的消息传递花费的时间最长,为 44 个单位时间。
package main
import (
"fmt"
)
const N = 20010
const M = 20010
var ans,idx int
var h = make([]int,N)
var e = make([]int,M)
var ne = make([]int,M)
func max( a , b int) int {
if a > b {
return a
}
return b
}
func add( a , b int ){
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx ++
}
func dfs( idx int ) int {
var d1 , d2 int
i := h[idx]
for i != - 1 {
j := e[i]
d := dfs(j)
if d >= d1{
d2 = d1
d1 = d
}else if d > d2{
d2 = d
}
i = ne[i]
}
ans = max( ans , d1 + d2)
return d1 + 1
}
func main(){
var n, m int
fmt.Scanf("%d %d",&n, &m)
for i:= range h {
h[i] = -1
}
for i := 2 ; i <= n + m ; i ++{
var p int
fmt.Scanf("%d" , &p)
add(p ,i)
}
dfs(1)
fmt.Println(ans)
}