CF 958B1 - Maximum Control (easy)
Rating: 1000
Tags: implementation
Model: gpt-5-3-mini
Solve time: 1m 17s
Verified: yes (1/1 samples)
Share: https://chatgpt.com/share/6a327e68-d164-83ec-b8c1-6a5c68225db7
Solution
Problem Understanding
We are given a network of planets connected by tunnels, forming a tree structure. This means every planet is reachable from every other planet, and between any two planets there is exactly one simple path.
A planet is called remote if it connects to the rest of the system through exactly one tunnel. In graph terms, this is a vertex with degree equal to one, a leaf in the tree.
The task is simply to count how many such remote planets exist.
The input size is up to 1000 planets. Even a quadratic solution with around 10^6 operations would easily run within limits, but the structure of the problem suggests something simpler: we only need local information about each node, not any global traversal or path computation.
A few edge cases matter in trees:
If the tree is a line like 1 - 2 - 3 - 4, the remote planets are the two endpoints. A naive misunderstanding might try to consider “distance” or “depth”, but that is irrelevant.
If the tree has only two nodes connected by one edge, both nodes have degree one, so both are remote, and the answer is 2. A mistake here often comes from assuming leaves must be “less than two neighbors”, but forgetting that degree one applies even in the smallest tree.
If the tree is a star centered at node 1 connected to all others, then all outer nodes are remote, and the center is not.
Approaches
A brute-force approach would be to treat each node as a candidate and count how many neighbors it has by scanning all edges for every node. For each of N nodes, we scan up to N edges, giving O(N^2) operations. With N up to 1000, this is around 10^6 checks, which is still acceptable, but unnecessary.
However, the structure of a tree makes this simpler. Each node’s number of connections is exactly its degree. Instead of repeatedly scanning edges, we can maintain a degree array. Every time we read an edge (u, v), we increment degree[u] and degree[v]. After processing all edges, we just count how many nodes have degree equal to 1.
The key insight is that the definition of “remote” depends only on immediate connectivity, not on any global property of the tree. Once degrees are known, the answer is obtained in linear time.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force (scan edges per node) | O(N^2) | O(N + E) | Accepted |
| Degree counting | O(N) | O(N) | Accepted |
Algorithm Walkthrough
- Read the number of planets N. This determines how many nodes we will track in our degree array.
- Create an array degree of size N + 1 initialized to zero. This will store how many tunnels are incident to each planet.
- Read each of the N − 1 tunnels. For each tunnel between u and v, increment degree[u] and degree[v]. This works because each tunnel contributes exactly one connection to both endpoints.
- After processing all tunnels, iterate over all planets from 1 to N.
- Count how many planets have degree equal to 1. These are exactly the remote planets because they are connected to the tree through a single edge.
- Output the count.
Why it works
In a tree, every edge contributes exactly one to the degree of each of its endpoints, and there are no duplicate edges or self-loops. Therefore, the degree array fully captures the structure of local connectivity. A node with degree 1 has exactly one neighbor, meaning removing its only edge disconnects it from the rest of the tree. No other node can satisfy the “connected via only one tunnel” condition.
Python Solution
import sys
input = sys.stdin.readline
def solve():
n = int(input())
deg = [0] * (n + 1)
for _ in range(n - 1):
u, v = map(int, input().split())
deg[u] += 1
deg[v] += 1
ans = 0
for i in range(1, n + 1):
if deg[i] == 1:
ans += 1
print(ans)
if __name__ == "__main__":
solve()
The implementation relies entirely on tracking degrees. The adjacency structure is never explicitly stored, which avoids unnecessary memory overhead. The loop over edges is responsible only for updating counts, which ensures we never revisit the same information twice. The final scan is a direct classification step over precomputed degrees.
A common mistake is trying to perform a DFS or BFS and interpret “leafness” dynamically. That is unnecessary here because the tree structure is already fully known, and degree alone is sufficient.
Worked Examples
Example 1
Input:
5
4 1
4 2
1 3
1 5
We build degree counts:
| Step | Edge | deg[1] | deg[2] | deg[3] | deg[4] | deg[5] |
|---|---|---|---|---|---|---|
| 1 | 4-1 | 1 | 0 | 0 | 1 | 0 |
| 2 | 4-2 | 1 | 1 | 0 | 2 | 0 |
| 3 | 1-3 | 2 | 1 | 1 | 2 | 0 |
| 4 | 1-5 | 3 | 1 | 1 | 2 | 1 |
Nodes with degree 1 are 2, 3, and 5, so the answer is 3.
This confirms that leaves in a star-like structure are correctly identified purely through degree counting.
Example 2
Input:
4
1 2
2 3
3 4
| Step | Edge | deg[1] | deg[2] | deg[3] | deg[4] |
|---|---|---|---|---|---|
| 1 | 1-2 | 1 | 1 | 0 | 0 |
| 2 | 2-3 | 1 | 2 | 1 | 0 |
| 3 | 3-4 | 1 | 2 | 2 | 1 |
Leaves are nodes 1 and 4, giving answer 2.
This shows that in a linear chain, only endpoints qualify as remote planets.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(N) | Each edge is processed once, and each node is checked once |
| Space | O(N) | Degree array of size N + 1 |
The constraints allow up to 1000 nodes, so both time and memory usage are trivially small. Even a more complex approach would fit, but this solution stays close to the structure of the problem and avoids unnecessary computation.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
from collections import deque
n = int(input())
deg = [0] * (n + 1)
for _ in range(n - 1):
u, v = map(int, input().split())
deg[u] += 1
deg[v] += 1
ans = sum(1 for i in range(1, n + 1) if deg[i] == 1)
return str(ans)
# provided sample
assert run("""5
4 1
4 2
1 3
1 5
""") == "3"
# minimum tree
assert run("""2
1 2
""") == "2"
# chain
assert run("""4
1 2
2 3
3 4
""") == "2"
# star
assert run("""5
1 2
1 3
1 4
1 5
""") == "4"
# skewed tree
assert run("""6
1 2
2 3
3 4
4 5
5 6
""") == "2"
| Test input | Expected output | What it validates |
|---|---|---|
| 2-node tree | 2 | smallest valid case |
| chain tree | 2 | endpoints only |
| star tree | 4 | all leaves counted correctly |
| linear 6-node chain | 2 | no off-by-one in degree counting |
Edge Cases
A two-node tree is the most fragile case. Input:
2
1 2
After processing the only edge, both deg[1] and deg[2] become 1. The algorithm counts both, returning 2. This avoids a common bug where solutions assume leaves must have at least two neighbors overall in a “bigger” tree.
A straight-line tree tests whether endpoints are correctly detected without any special-case logic. For a chain, only the first and last nodes accumulate exactly one connection. Intermediate nodes always accumulate two, so they are correctly excluded.
A star-shaped tree ensures that high-degree central nodes are not mistakenly included. The center accumulates N − 1 connections and is naturally filtered out, while all others remain degree one and are counted.