分数: 100 点
问题陈述
你得到了一棵有根的树 N 顶点。顶点编号从 1 to N,带顶点 1 是根。 i第一条边连接顶点 A_i 和顶点 B_i.
为每个顶点分配一种颜色,以满足以下条件:
- 让顶点的颜色 i be c_i。对于任意三个不同的顶点 u, v,和 w,如果 w = \mathrm{lca}(u, v) 和 c_u = c_v,那么 c_u \neq c_w.
找出所使用的不同颜色的最小可能数量。
在这里, \mathrm{lca}(u, v) 表示顶点的最低共同祖先 u 和 v.
约束
- 所有输入值均为整数。
- 3 \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 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
例如,下面所示的着色满足给定的条件。
由于无法使用两种或更少的颜色来满足条件,因此所需的最小颜色数为 3.
示例输入 2
4 1 2 2 3 3 4
示例输出 2
1