B1. Maximum Control (easy)

Codeforces

IDCF958B1

Time2000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

The Resistance is trying to take control over all planets in a particular solar system. This solar system is shaped like a tree. More precisely, some planets are connected by bidirectional hyperspace tunnels in such a way that there is a path between every pair of the planets, but removing any tunnel would disconnect some of them. The Resistance already has measures in place that will, when the time is right, enable them to control every planet that is not _remote_. A planet is considered to be remote if it is connected to the rest of the planets only via a single hyperspace tunnel. How much work is there left to be done: that is, how many remote planets are there? ## Input The first line of the input contains an integer _N_ (2 ≤ _N_ ≤ 1000) – 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 A single integer denoting the number of remote planets. [samples] ## Note In the first example, only planets 2, 3 and 5 are connected by a single tunnel. In the second example, the _remote_ planets are 2 and 3. Note that this problem has only two versions – easy and medium.

抵抗组织正试图控制某个恒星系统中的所有行星。这个恒星系统呈树状结构。更准确地说，某些行星通过双向超空间隧道相连，使得任意两个行星之间都存在路径，但移除任意一条隧道都会导致部分行星断开连接。抵抗组织已经部署了措施，当时机成熟时，将能够控制所有非_偏远_的行星。一个行星被认为是偏远的，当且仅当它仅通过一条超空间隧道与其他行星相连。那么，还剩多少工作要做：即，有多少个偏远行星？输入的第一行包含一个整数 #cf_span[N] (#cf_span[2 ≤ N ≤ 1000]) —— 星系中行星的数量。接下来的 #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[2]、#cf_span[3] 和 #cf_span[5] 通过单条隧道连接。在第二个示例中，_偏远_ 的行星是 #cf_span[2] 和 #cf_span[3]。注意：本题仅有两个版本——简单版和中等版。 ## Input 输入的第一行包含一个整数 #cf_span[N] (#cf_span[2 ≤ N ≤ 1000]) —— 星系中行星的数量。接下来的 #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 输出一个整数，表示偏远行星的数量。 [samples] ## Note 在第一个示例中，只有行星 #cf_span[2]、#cf_span[3] 和 #cf_span[5] 通过单条隧道连接。在第二个示例中，_偏远_ 的行星是 #cf_span[2] 和 #cf_span[3]。注意：本题仅有两个版本——简单版和中等版。

**Definitions** Let $ G = (V, E) $ be an undirected tree with $ |V| = N $ vertices (planets) and $ |E| = N - 1 $ edges (hyperspace tunnels). **Constraints** 1. $ 2 \leq N \leq 1000 $ 2. $ G $ is connected and acyclic (tree structure). 3. Each edge connects a distinct pair of vertices. **Objective** Compute the number of **remote planets**, defined as vertices of degree 1 in $ G $: $$ \left| \left\{ v \in V \mid \deg(v) = 1 \right\} \right| $$

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B1. Maximum Control (easy)",
    "description": {
      "content": "The Resistance is trying to take control over all planets in a particular solar system. This solar system is shaped like a tree. More precisely, some planets are connected by bidirectional hyperspace ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF958B1"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Resistance is trying to take control over all planets in a particular solar system. This solar system is shaped like a tree. More precisely, some planets are connected by bidirectional hyperspace ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "抵抗组织正试图控制某个恒星系统中的所有行星。这个恒星系统呈树状结构。更准确地说，某些行星通过双向超空间隧道相连，使得任意两个行星之间都存在路径，但移除任意一条隧道都会导致部分行星断开连接。\n\n抵抗组织已经部署了措施，当时机成熟时，将能够控制所有非_偏远_的行星。一个行星被认为是偏远的，当且仅当它仅通过一条超空间隧道与其他行星相连。\n\n那么，还剩多少工作要做：即，有多少个偏远行星？\n\n输入的第一行包...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected tree with $ |V| = N $ vertices (planets) and $ |E| = N - 1 $ edges (hyperspace tunnels).\n\n**Constraints**  \n1. $ 2 \\leq N \\leq 1000 $  \n2. $ G $ i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments