Funcia
Lv.3dfsdptreetree-dp

Non-Adjacent Villages on a Tree

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

peopleroadsresult
[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

  • 1≤N=1 \le N = people.length ≤200,000\le 200{,}000, 1≤1 \le people[i] ≤109\le 10^9
  • roads.length =N−1= N - 1, 0≤0 \le a, b <N< N, a ≠\ne b; the roads form a tree
  • The answer may exceed 32 bits.

Expected complexity

Time
O(N)
Space
O(N)

Examples

peopleroadsExpected
[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 O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)230 msestimated
C++ (GCC, gnu++23)230 msderived
Python 3.131000 msderived
Java 251568 msderived
Kotlin 2.4 (JVM)1460 msestimated
C# 14 (.NET 10)1460 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.