Score : $600$ points

问题描述

你给定一棵包含 $N$ 个顶点的树，顶点编号从 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

求一个最小整数 $K$，使得你可以为每个顶点涂色，使得以下两个条件得到满足。你可以使用任意数量的颜色。

• 对于每种颜色，该颜色涂过的顶点集合是连通的，并且构成一条简单路径。
• 对于树上的所有简单路径，路径中的顶点颜色至多有 $K$ 种不同颜色。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 12:13:13