#P12919. [AGC009D] Uninity

    ID: 12103 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-树形 DP状压 DP位集求交位集求并消除被支配候选

[AGC009D] Uninity

AT_agc009_d

题目描述

如下递归地定义一棵树的“ウニ度”kk:

  • 仅包含 11 个顶点的树,其ウニ度为 00。
  • 准备若干棵ウニ度为 kk 的树(可以为 00 棵),再准备一个顶点 vv。从每棵ウニ度为 kk 的树中各选一个顶点,并将这些顶点与 vv 分别用边连接。这样得到的树,其ウニ度为 k+1k+1。

可以证明,ウニ度为 kk 的树同时也是ウニ度为 k+1,k+2,…k+1,k+2,\ldots 的树。

给定一棵包含 NN 个顶点的树。树的顶点编号为 11 到 NN,第 ii 条边连接顶点 aia_i 和 bib_i。

请你求出使得该树为ウニ度 kk 的最小 kk。

输入格式

输入按以下格式从标准输入读入:

NN
a1a_1 b1b_1
a2a_2 b2b_2
⋮\vdots
aN−1a_{N-1} bN−1b_{N-1}

输出格式

输出使得给定树为ウニ度 kk 的最小 kk。

输入输出样例 #1

输入 #1

7
1 2
2 3
2 4
4 6
6 7
7 5

输出 #1

2

输入输出样例 #2

输入 #2

12
1 2
2 3
2 4
4 5
5 6
6 7
7 8
5 9
9 10
10 11
11 12

输出 #2

3

说明/提示

限制条件

  • 2≤N≤1052 \leq N \leq 10^5
  • 1≤ai,bi≤N (1≤i≤N−1)1 \leq a_i, b_i \leq N\ (1 \leq i \leq N-1)
  • 输入保证是一棵树。

样例解释 1

可以将顶点 11、33、44 各自作为ウニ度 00 的树,与顶点 22 组合,得到包含顶点 1,2,3,41,2,3,4 的ウニ度 11 的树;顶点 55 作为ウニ度 00 的树,与顶点 77 组合,得到包含顶点 5,75,7 的ウニ度 11 的树;再将包含顶点 1,2,3,41,2,3,4 的ウニ度 11 的树、包含顶点 5,75,7 的ウニ度 11 的树与顶点 66 组合,得到包含顶点 1,2,3,4,5,6,71,2,3,4,5,6,7 的ウニ度 22 的树。