B2. Maximum Control (medium)

Codeforces

IDCF958B2

Time3000ms

Memory256MB

Difficulty—

data structuresdfs and similargraphsgreedytrees

English · Original

Chinese · Translation

Formal · Original

The Resistance is trying to take control over as many planets of a particular solar system as possible. Princess Heidi is in charge of the fleet, and she must send ships to some planets in order to maximize the number of controlled planets. The Galaxy contains _N_ planets, connected by bidirectional hyperspace tunnels in such a way that there is a unique path between every pair of the planets. A planet is controlled by the Resistance if there is a Resistance ship in its orbit, or if the planet lies on the shortest path between some two planets that have Resistance ships in their orbits. Heidi has not yet made up her mind as to how many ships to use. Therefore, she is asking you to compute, for every _K_ = 1, 2, 3, ..., _N_, the maximum number of planets that can be controlled with a fleet consisting of _K_ ships. ## Input The first line of the input contains an integer _N_ (1 ≤ _N_ ≤ 105) – the number of planets in the galaxy. The next _N_ - 1 lines describe the hyperspace tunnels between the planets. Each of the _N_ - 1 lines contains two space-separated integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _N_) indicating that there is a bidirectional hyperspace tunnel between the planets _u_ and _v_. It is guaranteed that every two planets are connected by a path of tunnels, and that each tunnel connects a different pair of planets. ## Output On a single line, print _N_ space-separated integers. The _K_\-th number should correspond to the maximum number of planets that can be controlled by the Resistance using a fleet of _K_ ships. [samples] ## Note Consider the first example. If _K_ = 1, then Heidi can only send one ship to some planet and control it. However, for _K_ ≥ 2, sending ships to planets 1 and 3 will allow the Resistance to control all planets.

抵抗组织正试图控制某个星系中的尽可能多的行星。海蒂公主负责舰队，她必须向某些行星派遣飞船，以最大化被控制的行星数量。银河系包含 #cf_span[N] 个行星，这些行星通过双向超空间隧道连接，使得任意两个行星之间存在唯一路径。如果一个行星的轨道上有抵抗组织的飞船，或者该行星位于某两个拥有抵抗组织飞船的行星之间的最短路径上，则该行星被抵抗组织控制。海蒂尚未决定使用多少艘飞船。因此，她要求你计算，对于每一个 #cf_span[K = 1, 2, 3, ..., N]，使用由 #cf_span[K] 艘飞船组成的舰队最多能控制多少个行星。输入的第一行包含一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 105]) —— 星系中行星的数量。接下来的 #cf_span[N - 1] 行描述了行星之间的超空间隧道。每条 #cf_span[N - 1] 行包含两个用空格分隔的整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ N])，表示行星 #cf_span[u] 和 #cf_span[v] 之间存在一条双向超空间隧道。保证任意两个行星之间都存在由隧道构成的路径，且每条隧道连接一对不同的行星。在一行中输出 #cf_span[N] 个用空格分隔的整数。第 #cf_span[K] 个数应对应于使用由 #cf_span[K] 艘飞船组成的舰队时抵抗组织最多能控制的行星数量。考虑第一个示例。如果 #cf_span[K = 1]，则海蒂只能将一艘飞船发送到某个行星并控制它。然而，对于 #cf_span[K ≥ 2]，将飞船发送到行星 1 和 3 将使抵抗组织能够控制所有行星。 ## Input 输入的第一行包含一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 105]) —— 星系中行星的数量。接下来的 #cf_span[N - 1] 行描述了行星之间的超空间隧道。每条 #cf_span[N - 1] 行包含两个用空格分隔的整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ N])，表示行星 #cf_span[u] 和 #cf_span[v] 之间存在一条双向超空间隧道。保证任意两个行星之间都存在由隧道构成的路径，且每条隧道连接一对不同的行星。 ## Output 在一行中输出 #cf_span[N] 个用空格分隔的整数。第 #cf_span[K] 个数应对应于使用由 #cf_span[K] 艘飞船组成的舰队时抵抗组织最多能控制的行星数量。 [samples] ## Note 考虑第一个示例。如果 #cf_span[K = 1]，则海蒂只能将一艘飞船发送到某个行星并控制它。然而，对于 #cf_span[K ≥ 2]，将飞船发送到行星 1 和 3 将使抵抗组织能够控制所有行星。

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of planets. Let $ T = (V, E) $ be a tree with $ |V| = N $, where each vertex represents a planet and each edge represents a bidirectional hyperspace tunnel. Let $ S \subseteq V $ be a subset of vertices (planets) where Resistance ships are placed, with $ |S| = K $. The set of *controlled planets* is the union of $ S $ and all vertices lying on any simple path between two vertices in $ S $. Equivalently, the controlled set is the vertex set of the minimal subtree of $ T $ that spans $ S $, denoted $ \text{Steiner}(S) $. **Constraints** 1. $ 1 \leq N \leq 10^5 $ 2. $ T $ is a tree (connected, acyclic, undirected) **Objective** For each $ K \in \{1, 2, \dots, N\} $, compute: $$ f(K) = \max_{\substack{S \subseteq V \\ |S| = K}} \left| \text{Steiner}(S) \right| $$ That is, the maximum number of vertices in the minimal subtree spanning any subset of $ K $ vertices in $ T $.

Samples

Input #1

3
1 2
2 3

Output #1

1 3 3

Input #2

Output #2

1 3 4 4

API Response (JSON)

{
  "problem": {
    "name": "B2. Maximum Control (medium)",
    "description": {
      "content": "The Resistance is trying to take control over as many planets of a particular solar system as possible. Princess Heidi is in charge of the fleet, and she must send ships to some planets in order to ma",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF958B2"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Resistance is trying to take control over as many planets of a particular solar system as possible. Princess Heidi is in charge of the fleet, and she must send ships to some planets in order to ma...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "抵抗组织正试图控制某个星系中的尽可能多的行星。海蒂公主负责舰队，她必须向某些行星派遣飞船，以最大化被控制的行星数量。\n\n银河系包含 #cf_span[N] 个行星，这些行星通过双向超空间隧道连接，使得任意两个行星之间存在唯一路径。\n\n如果一个行星的轨道上有抵抗组织的飞船，或者该行星位于某两个拥有抵抗组织飞船的行星之间的最短路径上，则该行星被抵抗组织控制。\n\n海蒂尚未决定使用多少艘飞船。因此，她要求...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of planets.  \nLet $ T = (V, E) $ be a tree with $ |V| = N $, where each vertex represents a planet and each edge represents a bidirectional h...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments