最优路径分解

题目描述

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

求最小的整数 $K$，使得可以用颜色给每个顶点染色，满足以下两个条件。颜色种类数不限。

对于每种颜色，染成该颜色的顶点集合是连通的，并且构成一条简单路径。

对于树上的所有简单路径，路径中顶点的不同颜色数至多为 $K$。

输入格式

输入按以下格式从标准输入给出：

$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 \le 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

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le N$
• 给定的图是一棵树
• 输入中的所有值均为整数