L. PC is for kicking

Codeforces

IDCF10187L

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Otvio is a calm guy with a guilty pleasure: kicking PCs. Now he is participating in a programming competition where the computers are arranged as a tree, that is, the N PCs are connected by N - 1 cables and there is only one cable path from one PC to another. Otvio wants to kick as many PCs as possible. To do so, he will walk along a cable path, kicking all the PCs in the path. He will start at PC a, the one he will use in the contest. However, to prevent getting caught, he will not pass by PCs he already kicked nor kick any PC twice. Laerco, knowing Otvio's guilty pleasure, wants to know the maximum number of PCs Otvio can kick satisfying the conditions above. Remember that Otvio will kick his own PC for sure. The first line of the input consist of two integers integer N and a (1 ≤ N, a ≤ 105), the number of PCs in the contest and the number of Otvio's PC, in this order. Each of the next N - 1 lines contains two integers u and v (1 ≤ u, v ≤ N), indicating that there is a cable connecting PCs u and v. Output a single integer - the maximum number of PCs Otvio can kick. ## Input The first line of the input consist of two integers integer N and a (1 ≤ N, a ≤ 105), the number of PCs in the contest and the number of Otvio's PC, in this order. Each of the next N - 1 lines contains two integers u and v (1 ≤ u, v ≤ N), indicating that there is a cable connecting PCs u and v. ## Output Output a single integer - the maximum number of PCs Otvio can kick. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of PCs, and $ a \in \{1, \dots, N\} $ be the starting PC. Let $ T = (V, E) $ be a tree with vertex set $ V = \{1, \dots, N\} $ and edge set $ E $ of size $ N-1 $. **Constraints** 1. $ 1 \leq N \leq 10^5 $ 2. $ 1 \leq a \leq N $ 3. Each edge $ (u, v) \in E $ connects distinct vertices $ u, v \in V $. **Objective** Find the maximum number of vertices in a simple path starting at vertex $ a $ in tree $ T $. That is, compute the length (in vertices) of the longest path beginning at $ a $, where no vertex is revisited. This is equivalent to: $$ \max_{P \in \mathcal{P}_a} |P| $$ where $ \mathcal{P}_a $ is the set of all simple paths in $ T $ starting at $ a $. Equivalently, it is the maximum distance (in vertices) from $ a $ to any leaf in $ T $, where distance is measured as the number of vertices along the path.

API Response (JSON)

{
  "problem": {
    "name": "L. PC is for kicking",
    "description": {
      "content": "Otvio is a calm guy with a guilty pleasure: kicking PCs. Now he is participating in a programming competition where the computers are arranged as a tree, that is, the N PCs are connected by N - 1 cabl",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10187L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Otvio is a calm guy with a guilty pleasure: kicking PCs. Now he is participating in a programming competition where the computers are arranged as a tree, that is, the N PCs are connected by N - 1 cabl...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of PCs, and $ a \\in \\{1, \\dots, N\\} $ be the starting PC.  \nLet $ T = (V, E) $ be a tree with vertex set $ V = \\{1, \\dots, N\\} $ and edge set...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments