Non-Adjacent Villages on a Tree
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
N villages numbered 0 to N - 1 are connected by N - 1 roads so that every pair of villages is joined by
exactly one path (a tree). people[i] is the population of village i and roads[j] = [a, b] is a road between
villages a and b.
Choose villages to host a festival so that no two chosen villages are directly connected by a road. Return the maximum total population of the chosen villages.
Examples
| people | roads | result |
|---|---|---|
[10, 1, 1, 1] | [[0, 1], [0, 2], [0, 3]] | 10 |
[1, 5, 5, 5] | [[0, 1], [0, 2], [0, 3]] | 15 |
[3, 2, 1, 10, 1] | [[0, 1], [1, 2], [2, 3], [3, 4]] | 13 |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(people: int[], roads: int[][]) → long
Constraints
-
people.length,people[i] roads.length,a,b,ab; the roads form a tree- The answer may exceed 32 bits.
Expected complexity
- Time
- O(N)
- Space
- O(N)
Examples
| people | roads | Expected |
|---|---|---|
[10,1,1,1] | [[0,1],[0,2],[0,3]] | 10 |
[1,5,5,5] | [[0,1],[0,2],[0,3]] | 15 |
[3,2,1,10,1] | [[0,1],[1,2],[2,3],[3,4]] | 13 |
Hint
Hint
Root the tree and compute, bottom-up, take[v] = people[v] + Σ skip[c] and skip[v] = Σ max(take[c], skip[c]) over
children c; the answer is max(take[root], skip[root]). A path-shaped tree is 200,000 deep, so use an explicit stack or
reverse BFS order instead of recursion. Scanning the whole road list to find each village's neighbours is and
exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 230 ms | estimated |
| C++ (GCC, gnu++23) | 230 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1568 ms | derived |
| Kotlin 2.4 (JVM) | 1460 ms | estimated |
| C# 14 (.NET 10) | 1460 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |