G - Coloring Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 100 points

Problem Statement

You are given a rooted tree with N vertices. The vertices are numbered from 1 to N, with vertex 1 being the root. The i-th edge connects vertex A_i and vertex B_i.

Assign a color to each vertex such that the following condition is satisfied:

  • Let the color of vertex i be c_i. For any three distinct vertices u, v, and w, if w = \mathrm{lca}(u, v) and c_u = c_v, then c_u \neq c_w.

Find the minimum possible number of distinct colors used.

Here, \mathrm{lca}(u, v) denotes the lowest common ancestor of vertices u and v.

Constraints

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

Input

The input is given in the following format:

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

Output

Print the minimum number of distinct colors required.

Sample Input 1

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

Sample Output 1

3

For example, the coloring shown below satisfies the given conditions.

Since there is no way to satisfy the conditions using two or fewer colors, the minimum number of colors needed is 3.

Sample Input 2

4
1 2
2 3
3 4

Sample Output 2

1

配点 : 100 点

問題文

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

木の各頂点に対し、次の条件を満たすように色を塗ります。

  • 頂点 i の色を c_i とする。任意の相異なる 3 頂点 u, v, w について、「 w = \mathrm{lca}(u, v) かつ c_u = c_v ならば c_u \neq c_w 」 が成り立つ。

このとき、使用した色の種類数としてありうる最小値を求めてください。

ここで、\mathrm{lca}(u, v) は頂点 u と頂点 v の最小共通祖先を表します。

制約

  • 入力はすべて整数
  • 3 ≤ N ≤ 2 \times 10^5
  • 1 ≤ A_i, B_i ≤ N
  • 入力されるグラフは木

入力

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

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

出力

答えを出力せよ。

入力例 1

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

出力例 1

3

例えば、下図のように色を塗ると、与えられた条件を満たします。

2 色以下で条件を満たすように頂点を塗り分ける方法は存在しないため、使う色の種類数の最小値は 3 となります。

入力例 2

4
1 2
2 3
3 4

出力例 2

1