J. Protecting Fancouver

Codeforces

IDCF10187J

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Friendo is a super hero that protects the city of Fancouver from bad games. He knows that a new game from the Velda franchise - one that tricks people into thinking it's good and makes them go crazy - will be released in the next few days and is going to be sold at N game stores. In Fancouver, the game stores have a mafia and are connected in such a way that there is always one path and only one path from one to another, so that when you want to go to from one game store to another, you may have to visit stores you didn't want to visit and end up buying games you didn't want to buy. With his power, Friendo can destroy any number of stores, as long as the distance between any two of them is at most K. What is the largest number of stores that Friendo can destroy? The input starts with a single line containing two integers N and K (1 ≤ K < N ≤ 105). Each of the following N - 1 lines contains two integers u, v (1 ≤ u < v ≤ N) indicating that game store u is connected to game store v. Output a single integer that indicates the largest number of game stores Friendo can destroy. ## Input The input starts with a single line containing two integers N and K (1 ≤ K < N ≤ 105). Each of the following N - 1 lines contains two integers u, v (1 ≤ u < v ≤ N) indicating that game store u is connected to game store v. ## Output Output a single integer that indicates the largest number of game stores Friendo can destroy. [samples]

**Definitions** Let $ S(x) $ be a word defined recursively over alphabet $ \Sigma = \{a, b, \dots, z\} $: - $ S(a) = "a" $ - For $ x \ne a $, let $ p(x) $ be the predecessor of $ x $ in the alphabet; then $$ S(x) = S(p(x)) + x + S(p(x)) $$ **Constraints** - $ 1 \le n \le 2^{25} - 1 $ (length of $ S(z) $) **Objective** Find the $ n $-th character (1-indexed) of $ S(z) $.

API Response (JSON)

{
  "problem": {
    "name": "J. Protecting Fancouver",
    "description": {
      "content": "Friendo is a super hero that protects the city of Fancouver from bad games. He knows that a new game from the Velda franchise - one that tricks people into thinking it's good and makes them go crazy -",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10187J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Friendo is a super hero that protects the city of Fancouver from bad games. He knows that a new game from the Velda franchise - one that tricks people into thinking it's good and makes them go crazy -...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S(x) $ be a word defined recursively over alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $:  \n- $ S(a) = \"a\" $  \n- For $ x \\ne a $, let $ p(x) $ be the predecessor of $ x $ in the alph...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments