B. Dynamic Diameter

Codeforces

IDCF10269B

Time3000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given $n + 1$ nodes and $n -1$ edges where the first $n$ nodes are a tree and node $n + 1$ is in its own component. For each node $i$ from $1... n$, answer the following question: If an edge was added from node $i$ to node $n + 1$, what would the diameter of the created tree be? (Notice that the $n + 1$ nodes will be a tree if this edge was added). The first line will contain a single integer $n$, the number of nodes in the tree initial tree. $n -1$ lines follow, each containing two different integers, describing the edges initially in the tree. Additional constraint on input: these edges will form a tree on the first $n$ nodes. $1 <= n <= 3 * 10^5$ Print $n$ integers, each on their own line. The $i$th is the diameter of the new tree if you were to add an edge from node $i$ to node $n + 1$. ## Input The first line will contain a single integer $n$, the number of nodes in the tree initial tree. $n -1$ lines follow, each containing two different integers, describing the edges initially in the tree. Additional constraint on input: these edges will form a tree on the first $n$ nodes.$1 <= n <= 3 * 10^5$ ## Output Print $n$ integers, each on their own line. The $i$th is the diameter of the new tree if you were to add an edge from node $i$ to node $n + 1$. [samples]

**Definitions** Let $ T = (V, E) $ be a tree with $ V = \{1, 2, \dots, n\} $ and $ |E| = n - 1 $. Let $ v_{n+1} $ be an isolated node. For each $ i \in \{1, \dots, n\} $, define $ T_i = (V \cup \{v_{n+1}\}, E \cup \{\{i, v_{n+1}\}\}) $, the tree formed by adding edge $ (i, v_{n+1}) $. **Constraints** $ 1 \le n \le 3 \cdot 10^5 $ **Objective** For each $ i \in \{1, \dots, n\} $, compute the diameter of $ T_i $, defined as: $$ \text{diam}(T_i) = \max_{u,v \in V \cup \{v_{n+1}\}} \text{dist}_{T_i}(u, v) $$

API Response (JSON)

{
  "problem": {
    "name": "B. Dynamic Diameter",
    "description": {
      "content": "You are given $n + 1$ nodes and $n -1$ edges where the first $n$ nodes are a tree and node $n + 1$ is in its own component. For each node $i$ from $1... n$, answer the following question: If an edge ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given $n + 1$ nodes and $n -1$ edges where the first $n$ nodes are a tree and node $n + 1$ is in its own component. For each node $i$ from $1... n$, answer the following question:\n\nIf an edge ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, n\\} $ and $ |E| = n - 1 $. Let $ v_{n+1} $ be an isolated node.  \n\nFor each $ i \\in \\{1, \\dots, n\\} $, define $ T_i = (V \\cup \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments