B. Bacteria Experiment

Codeforces

IDCF10152B

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A year after his bacteria experiment, Jason decided to perform another experiment on a new bacteria specie which evolves in a special way. The initial form of the bacteria can be considered as an undirected tree with N nodes in terms of graph theory. Every hour, an edge (x, y) is built if there exists a node z such that, in the previous hour, there exists edge (x, z) and edge (y, z), but not edge (x, y). The bacteria keep evolving until no more edges can be formed. The following graph shows a type of bacteria which requires 2 hours to fully evolve: As it may take months if not years for the bacteria to evolve to its ultimate form, it is impossible for Jason to stay at the laboratory to observe the change of the bacteria throughout the entire process. Therefore, he wants you to calculate the time required for the bacteria to fully evolve, so that he can just get back to the laboratory on time. The first line contains an integer N. (2 ≤ N ≤ 5 × 105) The next N - 1 line each contains two integers u and v, which means there exists an edge between node u and v. (1 ≤ u, v ≤ N) The given graph is guaranteed to be a valid tree. Output an integer, the time (in hours) required for the bacteria to fully evolve. ## Input The first line contains an integer N. (2 ≤ N ≤ 5 × 105)The next N - 1 line each contains two integers u and v, which means there exists an edge between node u and v. (1 ≤ u, v ≤ N)The given graph is guaranteed to be a valid tree. ## Output Output an integer, the time (in hours) required for the bacteria to fully evolve. [samples]

**Definitions** Let $ T = (V, E) $ be an undirected tree with $ |V| = N $ nodes and $ |E| = N - 1 $ edges. **Evolution Rule** At each hour, for any triple of distinct nodes $ (x, y, z) $, if edges $ (x, z) $ and $ (y, z) $ exist and $ (x, y) $ does not, then add edge $ (x, y) $. This process repeats until no more edges can be added. **Objective** Compute the number of hours required until the graph becomes a **complete graph** (i.e., all pairs of nodes are connected), starting from tree $ T $, under the above rule. **Constraints** - $ 2 \leq N \leq 5 \times 10^5 $ - The input graph is a tree. **Output** The number of hours until no more edges can be added.

API Response (JSON)

{
  "problem": {
    "name": "B. Bacteria Experiment",
    "description": {
      "content": "A year after his bacteria experiment, Jason decided to perform another experiment on a new bacteria specie which evolves in a special way. The initial form of the bacteria can be considered as an undi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10152B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A year after his bacteria experiment, Jason decided to perform another experiment on a new bacteria specie which evolves in a special way. The initial form of the bacteria can be considered as an undi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be an undirected tree with $ |V| = N $ nodes and $ |E| = N - 1 $ edges.  \n\n**Evolution Rule**  \nAt each hour, for any triple of distinct nodes $ (x, y, z) $, if ed...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments