← 返回题目列表

AtCoder · ttpc2024_2_g

G. 着色树

中文机器翻译题面 查看原题

分数: 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