L. Starry Night

Codeforces

IDCF10110L

Time6000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Reem likes to look up into the night sky and count how many stars there are. The sky is represented as a tree, and a star is a fixed node with three or more rays of possibly varying lengths leading out of it. A ray is a chain of connected nodes where each node except for the last one is connected to exactly two nodes, and the last one is connected to exactly one node. The first line of input contains a single integer T, the number of test cases. The first line of each test case contains a single integers N (1 ≤ N ≤ 105), the number of nodes in the sky. Each of the next N - 1 lines contains two integers a and b (1 ≤ a, b ≤ N), and represents a link that connects two nodes. It is guaranteed that the given graph is a tree. For each test case, print the maximum number of stars Reem can get after removing zero or more nodes, on a single line. A tree is an undirected graph with exactly one path between any two nodes. ## Input The first line of input contains a single integer T, the number of test cases.The first line of each test case contains a single integers N (1 ≤ N ≤ 105), the number of nodes in the sky.Each of the next N - 1 lines contains two integers a and b (1 ≤ a, b ≤ N), and represents a link that connects two nodes.It is guaranteed that the given graph is a tree. ## Output For each test case, print the maximum number of stars Reem can get after removing zero or more nodes, on a single line. [samples] ## Note A tree is an undirected graph with exactly one path between any two nodes.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ G = (V, E) $ be a tree with $ |V| = N $ nodes and $ |E| = N - 1 $ edges. A **star** is a node $ v \in V $ of degree $ \deg(v) \geq 3 $, such that each of its incident edges leads to a **ray**: a path (possibly of length 1) where all internal nodes (if any) have degree 2, and the terminal node has degree 1. **Constraints** 1. $ 1 \leq T \leq \text{unspecified} $ 2. For each test case: $ 1 \leq N \leq 10^5 $ 3. The graph is a tree. **Objective** Find the maximum number of stars that can be formed by removing zero or more nodes from the tree, such that each star is a node of degree $ \geq 3 $, and each of its incident edges extends into a valid ray (as defined). **Note**: Removal of a node also removes all incident edges. The goal is to maximize the count of such star nodes under the ray constraints.

API Response (JSON)

{
  "problem": {
    "name": "L. Starry Night",
    "description": {
      "content": "Reem likes to look up into the night sky and count how many stars there are. The sky is represented as a tree, and a star is a fixed node with three or more rays of possibly varying lengths leading ou",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10110L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Reem likes to look up into the night sky and count how many stars there are. The sky is represented as a tree, and a star is a fixed node with three or more rays of possibly varying lengths leading ou...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ G = (V, E) $ be a tree with $ |V| = N $ nodes and $ |E| = N - 1 $ edges.  \n\nA **star** is a node $ v...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments