You are given a rooted tree with n nodes labeled from 0 to n - 1, represented by an integer array parent of length n, where:
parent[0] = -1 (node 0 is the root).1 <= i < n, parent[i] is the parent of node i (0 <= parent[i] < i).You are also given an integer array nums of length n, where nums[i] is the value of node i, and an integer k.
A non-empty subset of nodes is called valid if:
k.Return the number of valid subsets modulo 109 + 7.
Example 1:
Input: parent = [-1,0,1], nums = [1,2,3], k = 3
Output: 1
Explanation:
The only valid subset is {2}. It contains node 2 with value 3, which is divisible by 3.
Example 2:
Input: parent = [-1,0,0,0], nums = [2,1,2,1], k = 3
Output: 2
Explanation:
The valid subsets are:
{1, 2}: Nodes 1 and 2 are both children of node 0 and not directly connected to each other. Their values sum to 1 + 2 = 3, which is divisible by 3.{2, 3}: Nodes 2 and 3 are also non-adjacent. Their values sum to 2 + 1 = 3, which is divisible by 3.No other subset satisfies both conditions. Therefore, the answer is 2.
Constraints:
n == parent.length == nums.length1 <= n <= 1000parent[0] == -11 <= i < n:
0 <= parent[i] < i1 <= nums[i] <= 1091 <= k <= 100parent describes a valid rooted tree.Problem Overview: Given a rooted tree, count how many subsets of nodes can be selected such that no two chosen nodes share a parent–child relationship. In graph terms, this asks for the number of independent sets in a tree.
Approach 1: Brute Force Subset Enumeration (O(2^n * n) time, O(n) space)
Generate every subset of nodes and check whether it contains an adjacent pair. For each subset, iterate through nodes and verify that no node and its parent are both selected. This guarantees correctness but becomes infeasible quickly because a tree with n nodes has 2^n possible subsets. Useful only for very small trees or for validating optimized solutions during testing.
Approach 2: Backtracking with Pruning (O(2^n) worst case, O(n) space)
Traverse nodes and decide whether to include or exclude each one. If you include a node, you must forbid selecting its parent and children. Maintaining a visited or restricted set allows pruning branches early. This reduces some redundant checks compared to full subset enumeration but still explores an exponential search space. Works for small trees where constraints allow aggressive pruning.
Approach 3: Tree Dynamic Programming with DFS (O(n) time, O(n) space)
The optimal solution uses dynamic programming on the tree structure. For each node u, compute two values: dp[u][0] (number of valid subsets in the subtree when u is excluded) and dp[u][1] (when u is included). If u is included, none of its children can be included, so multiply the dp[v][0] values of all children v. If u is excluded, each child can be either included or excluded, so multiply dp[v][0] + dp[v][1]. Compute these values using a depth‑first traversal of the tree with DFS. This structure works because trees have no cycles, making subtrees independent. The final answer is dp[root][0] + dp[root][1]. This technique is a classic example of tree DP.
Recommended for interviews: The DFS + tree DP approach. Interviewers expect you to recognize that the constraint "no adjacent nodes" maps directly to the independent set problem on trees. Starting from a brute force explanation shows you understand the constraint, but deriving the include/exclude DP demonstrates strong problem‑solving skills and knowledge of tree dynamic programming.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^n * n) | O(n) | Very small trees or verifying correctness during testing |
| Backtracking with Pruning | O(2^n) | O(n) | Small input sizes where pruning significantly reduces the search space |
| Tree DP with DFS | O(n) | O(n) | General case and interview settings; optimal for large trees |
Practice Count Non Adjacent Subsets in a Rooted Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor