提示: 欢迎访问OurACM平台。
Problem 1227 鸡毛信问题

Accept: 151    Submit: 545
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

大革命时期,地下党组织的联络图是一个树状结构。每个党员只和一个比他高一级的负责人单线联系,但他可以与若干个比他低一级的直接下属党员联系。紧急情况通常用鸡毛信传递。假设容易复制鸡毛信,但传递1 次鸡毛信需要1 个单位时间。试设计一个算法,计算从总负责人开始,传递鸡毛信到每个党员手中最少需要多少时间。

对于给定的地下党组织的联络图,计算从总负责人开始,传递鸡毛信到每个党员手中需的最少时间。

Input

第1行是党员总数n(1<n<50001)。全体党员编号为0,1,…,n-1。编号为0 的党员是总负责人。第2 行起共有n-1行,每行有2 个整数u 和v,表示党员u与党员v之间单线联系。

处理到文件末尾。

Output

传递鸡毛信到每个党员手中需的最少时间。

Sample Input

4 0 2 0 3 1 2

Sample Output

2

Source

FJ CFCS 2007

Submit  Back  Status  Discuss