Coloring Tree

AtCoder

IDttpc2024_2_g

Time2000ms

Memory256MB

Difficulty—

You are given a rooted tree with $N$ vertices. The vertices are numbered from $1$ to $N$, with vertex $1$ being the root. The $i$\-th edge connects vertex $A_i$ and vertex $B_i$. Assign a color to each vertex such that the following condition is satisfied: * Let the color of vertex $i$ be $c_i$. For any three distinct vertices $u$, $v$, and $w$, if $w = \mathrm{lca}(u, v)$ and $c_u = c_v$, then $c_u \neq c_w$. Find the minimum possible number of distinct colors used. Here, $\mathrm{lca}(u, v)$ denotes the lowest common ancestor of vertices $u$ and $v$. ## Constraints * All input values are integers. * $3 \leq N \leq 2 \times 10^5$ * $1 \leq A_i, B_i \leq N$ * The input graph is a tree. ## Input The input is given in the following format: $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_{N-1}$ $B_{N-1}$ [samples]

Samples

Input #1

Output #1

3

For example, the coloring shown below satisfies the given conditions.
Since there is no way to satisfy the conditions using two or fewer colors, the minimum number of colors needed is $3$.
![image](https://img.atcoder.jp/ttpc2024_2/956692bccf77f0df9d83837f5a7e95cb.svg)

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Coloring Tree",
    "description": {
      "content": "You are given a rooted tree with $N$ vertices. The vertices are numbered from $1$ to $N$, with vertex $1$ being the root. The $i$\\-th edge connects vertex $A_i$ and vertex $B_i$. Assign a color to eac",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "ttpc2024_2_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a rooted tree with $N$ vertices. The vertices are numbered from $1$ to $N$, with vertex $1$ being the root. The $i$\\-th edge connects vertex $A_i$ and vertex $B_i$.\nAssign a color to eac...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments