BZPRO
#2071. [POI2004]JAS
内存限制：64 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
在Byteotia有一个洞穴. 它包含n 个洞室和一些隧道连接他们. 每个洞室之间只有一条唯一的路径连接他们. Hansel 在其中一个洞室藏了宝藏, 但是它不会说出它在哪. Gretel 想知道. 当她询问一个洞室是否有宝藏时,如果她猜对了Hansel 会告诉她,如果猜错了他会告诉她哪个方向会有宝藏. 给出洞穴的信息,那么无论Hansel 把宝藏藏在了哪,求出最少要询问多少次才能找到宝藏.
输入格式
输入一个数n, 1<= n <= 50,000. 表示洞室总数,接下来n-1 行描述n – 1条边.
输出格式
输出一个数表示最少询问次数.
样例
样例输入
5
1 2
2 3
4 3
5 3
样例输出
2
数据范围与提示
BZPRO