I. Tree Game

Codeforces

IDCF10123I

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Consider the following game about coloring edges in a tree. You are given a tree. Initially, the color of all edges is white. Let a _valid path_ be a simple path such that all its edges are white, and the two endpoints are leaves in the tree. On each step of this game, you can choose a valid path and paint all its edges black. You cannot stop your game until you cannot find any valid path. The purpose of this game is to use the minimum number of steps to complete the game. Please find the minimum number of steps for the given tree. The first line of input contains one integer N indicating the number of nodes in the given tree. Each of the following N - 1 lines contains two integers x and y indicating that x-th node and y-th node are connected by an edge in the given tree. Nodes are numbered from 1 to N. Output one integer: the minimum number of steps required to complete the game on the given tree. ## Input The first line of input contains one integer N indicating the number of nodes in the given tree.Each of the following N - 1 lines contains two integers x and y indicating that x-th node and y-th node are connected by an edge in the given tree. Nodes are numbered from 1 to N. 2 ≤ N ≤ 105 1 ≤ x, y ≤ N the given graph is a tree ## Output Output one integer: the minimum number of steps required to complete the game on the given tree. [samples]

**Definitions** Let $ T = (V, E) $ be a tree with $ n = |V| $ nodes and $ n-1 $ edges. Let $ L \subseteq V $ be the set of leaf nodes (degree 1). An edge is initially white; coloring an edge black is irreversible. A *valid path* is a simple path between two distinct leaves such that all its edges are white. **Constraints** 1. $ n \geq 2 $ 2. The graph is a tree: connected, acyclic, undirected. 3. At each step, exactly one valid path is chosen and all its edges are colored black. 4. The game ends when no valid path exists (i.e., no path between two leaves with all-white edges remains). **Objective** Find the minimum number of valid paths needed to cover all edges of $ T $, such that every edge is included in at least one chosen path, and each chosen path connects two leaves.

API Response (JSON)

{
  "problem": {
    "name": "I. Tree Game",
    "description": {
      "content": "Consider the following game about coloring edges in a tree. You are given a tree. Initially, the color of all edges is white. Let a _valid path_ be a simple path such that all its edges are white, an",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10123I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider the following game about coloring edges in a tree.\n\nYou are given a tree. Initially, the color of all edges is white. Let a _valid path_ be a simple path such that all its edges are white, an...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n = |V| $ nodes and $ n-1 $ edges.  \nLet $ L \\subseteq V $ be the set of leaf nodes (degree 1).  \nAn edge is initially white; coloring an edge bla...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments