当前没有测试数据。

Ex - 最优路径分解

得分：$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}$

输出

输出答案。

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

3

如果 $K=3$，可以通过将顶点 $1,2,3,4$ 和 $5$ 着色为颜色 $1$，将顶点 $6$ 着色为颜色 $2$，将顶点 $7$ 着色为颜色 $3$，来满足条件。 如果 $K \leq 2$，没有办法对顶点着色满足条件，因此答案是 $3$。

6
3 5
6 4
6 3
4 2
1 5

1

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

3