Trail Signal Towers
Hard · tree dp
A nature park has n trail junctions, numbered 0 to n - 1. The n - 1 trails are given as edges, where each [a, b] is a trail between junctions a and b. You can walk from any junction to any other, and there is exactly one route between each pair, so the trails never form a loop.
A signal tower can be built at any junction. A tower covers its own junction and every junction that is joined to it directly by one trail.
Return the fewest towers needed so that every junction in the park is covered.
Examples
Example 1
Input: n = 1, edges = []
Output: 1
A single junction needs its own tower.
Example 2
Input: n = 5, edges = [[0, 1], [0, 2], [0, 3], [0, 4]]
Output: 1
One tower at junction 0 covers it and all four neighbours.
Example 3
Input: n = 7, edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]
Output: 3
Towers at 1, 4 and 6 cover junctions 0 to 2, 3 to 5 and 5 to 6. Two towers cannot cover seven junctions in a row.
Constraints
- 1 <= n <= 2000
- len(edges) == n - 1
- Each edge is [a, b] with 0 <= a, b < n and a != b.
- The trails connect all junctions and contain no loop.