#P2071. [POI2004]JAS

    ID: 1096 传统题 1000ms 64MiB 尝试: 79 已通过: 28 难度: 8 上传者: 标签>CF2500提高+/省选-树形 DP状压 DP位集求交位集求并支配关系Stage2

[POI2004]JAS

[POI2004] JAS

题目背景

在 Byteotia 有一个洞穴。

题目描述

它包含 nn 个洞室和一些隧道连接他们。

每个洞室之间只有一条唯一的路径连接他们。Hansel 在其中一个洞室藏了宝藏,但是它不会说出它在哪。Gretel 知道,当她询问一个洞室是否有宝藏时,如果她猜对了 Hansel 会告诉她,如果猜错了他会告诉她哪个方向会有宝藏。 给出洞穴的信息,那么无论 Hansel 把宝藏藏在了哪,求出最少要询问多少次才能找到宝藏。

输入格式

输入一个数 nn,表示洞室总数。

接下来 n−1n-1 行描述 n−1n-1 条边。

输出格式

输出一个数表示最少询问次数。

样例 #1

样例输入 #1

5
1 2
2 3
4 3
5 3

样例输出 #1

2

提示

对于 100%100\% 的数据,1≤n≤500001\le n\le50000。