AT_2_ttpc2024_2_g.Coloring Tree

现有一棵有根树，包含 $N$ 个顶点，顶点编号为 $1$ 到 $N$，其中顶点 $1$ 是根节点。每条边连接两个顶点，分别用 $A_i$ 和 $B_i$ 表示。

我们的任务是给这棵树的各个顶点着色，满足以下条件：

• 设定顶点 $i$ 的颜色为 $c_i$。对于任意三个不同的顶点 $u, v, w$，如果 $w$ 是 $u$ 和 $v$ 的最近公共祖先（记作 $w = \mathrm{lca}(u, v)$），并且 $u$ 和 $v$ 的颜色相同（即 $c_u = c_v$），那么它们的颜色必须与 $w$ 的颜色不同（即 $c_u \neq c_w$）。

在满足上述条件的前提下，求使用的最少颜色种类数。

其中，$\mathrm{lca}(u, v)$ 表示顶点 $u$ 和顶点 $v$ 的最近公共祖先。

输入的第一行为一个整数 $N$，表示树的顶点数。

接下来的 $N-1$ 行，每行包含两个整数 $A_i$ 和 $B_i$，表示树的一条边。

输出满足条件的最小颜色种类数。

• 所有输入值均为整数。
• $3 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$
• 输入表示一棵树。

示例解释

例如，下面的图片展示了一种符合条件的着色方法。由于无法使用少于 $3$ 种颜色满足所有条件，最少需要使用 $3$ 种颜色。

本翻译由 AI 自动生成