Ex - Optimal Path Decomposition Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点の木が与えられます。頂点には 1 から N までの番号がついており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。

各頂点に以下の条件を満たすように色を塗ることができる整数 K の最小値を求めてください。ただし、使える色の種類数に制限はありません。

  • 各色について、その色で塗られた頂点の集合は連結で単純パスをなす
  • 任意の木上の単純パスについて、そのパス内に含まれる頂点に塗られた色の種類数は K 以下

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • 与えられるグラフは木
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

出力

答えを出力せよ。

入力例 1

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

出力例 1

3

K = 3 のとき、頂点 1,2,3,4,5 を色 1、頂点 6 を色 2、頂点 7 を色 3 で塗るなどの方法で条件を満たすことができます。 K \leq 2 とすると条件を満たす色の塗り方は存在しないので答えは 3 です。

入力例 2

6
3 5
6 4
6 3
4 2
1 5

出力例 2

1

入力例 3

9
1 3
9 5
8 7
2 1
5 2
5 8
4 8
6 1

出力例 3

3

Score : 600 points

Problem Statement

You are given a tree with N vertices numbered 1 through N. The i-th edge connects vertex A_i and vertex B_i.

Find the minimum integer K such that you can paint each vertex in a color so that the following two conditions are satisfied. You may use any number of colors.

  • For each color, the set of vertices painted in the color is connected and forms a simple path.
  • For all simple paths on the tree, there are at most K distinct colors of the vertices in the path.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • The given graph is a tree.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

Output

Print the answer.

Sample Input 1

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

Sample Output 1

3

If K=3, the conditions can be satisfied by painting vertices 1,2,3,4, and 5 in color 1, vertex 6 in color 2, and vertex 7 in color 3. If K \leq 2, there is no way to paint the vertices to satisfy the conditions, so the answer is 3.

Sample Input 2

6
3 5
6 4
6 3
4 2
1 5

Sample Output 2

1

Sample Input 3

9
1 3
9 5
8 7
2 1
5 2
5 8
4 8
6 1

Sample Output 3

3