You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1, represented by an array parent where parent[i] is the parent of node i.
Each node i has three types of gates, given in a 2D array gates where gates[i] = [redi, bluei, whitei] which represents the number of red, blue, and white gates at node i.
Alice and Bob start at given nodes with either a red or blue card (1 = red, 0 = blue). They must independently move upward to their lowest common ancestor (LCA).
At each node, a person may move to their parent only if they can use at least one gate at that node with their current card. White gates may be used any number of times to flip the card color.
Movement rules (one move = from u to parent[u]):
u, pick exactly one specific gate instance. Identical gates are treated as separate and counted individually.u, the sequence ends.You are also given a 2D array queries where queries[i] = [aNodei, aCardi, bNodei, bCardi]:
aNodei, aCardi: Alice's starting node and card.bNodei, bCardi: Bob's starting node and card.For each query, count the number of distinct valid ways modulo 109 + 7 for both to reach their LCA.
After computing the result for all queries, return the bitwise XOR of those values.
Note:
a and b as the lowest node in a tree that has both a and b as descendants (where a node is allowed to be a descendant of itself).
Example 1:
Input: n = 3, parent = [-1,0,0], gates = [[1,0,1],[0,1,1],[1,1,0]], queries = [[1,0,2,0],[1,1,2,0],[1,0,2,1]]
Output: 1
Explanation:
i |
Alice [Node, Card] |
Bob [Node, Card] |
LCA | Alice Path |
Bob Path |
Alice Ways | Bob Ways | Total Ways |
|---|---|---|---|---|---|---|---|---|
| 0 | [1, 0]: Blue | [2, 0]: Blue | 0 | 1 → 0 | 2 → 0 | 2 (1 Blue + 1 White at node 1) | 1 (1 Blue at node 2) | 2 × 1 = 2 |
| 1 | [1, 1]: Red | [2, 0]: Blue | 0 | 1 → 0 | 2 → 0 | 1 (1 White at node 1) | 1 (1 Blue at node 2) | 1 × 1 = 1 |
| 2 | [1, 0]: Blue | [2, 1]: Red | 0 | 1 → 0 | 2 → 0 | 2 (1 Blue + 1 White at node 1) | 1 (1 Red at node 2) | 2 × 1 = 2 |
Thus, the XOR of all values: 2 XOR 1 XOR 2 = 1.
Example 2:
Input: n = 3, parent = [-1,0,1], gates = [[0,1,2],[1,0,1],[0,0,3]], queries = [[2,0,1,0],[2,1,0,0],[1,1,2,1]]
Output: 3
Explanation:
i |
Alice [Node, Card] |
Bob [Node, Card] |
LCA | Alice Path | Bob Path | Alice Ways | Bob Ways | Total Ways |
|---|---|---|---|---|---|---|---|---|
| 0 | [2, 0]: Blue | [1, 0]: Blue | 1 | 2 → 1 | 1 | 3 (3 White at node 2) | 1 (no move) | 3 × 1 = 3 |
| 1 | [2, 1]: Red | [0, 0]: Blue | 0 | 2 → 1 → 0 | 0 | 3 (3 White at node 2) × 1 (1 White at node 1) = 3 | 1 (no move) | 3 × 1 = 3 |
| 2 | [1, 1]: Red | [2, 1]: Red | 1 | 1 | 2 → 1 | 1 (no move) | 3 (3 White at node 2) | 1 × 3 = 3 |
Thus, the XOR of all values: 3 XOR 3 XOR 3 = 3.
Constraints:
2 <= n <= 2 * 104n == parent.length == gates.lengthparent[0] == -10 <= parent[i] < n for i in [1, n - 1]gates[i] == [redi, bluei, whitei]0 <= redi, bluei, whitei <= 101 <= queries.length <= 2 * 104queries[i] = [aNodei, aCardi, bNodei, bCardi]0 <= aNodei, bNodei <= n - 10 <= aCardi, bCardi <= 1parent represents a valid tree.Problem Overview: You are given a tree where certain nodes represent gates. For pairs or groups of nodes, determine how many distinct paths reach their lowest common ancestor (LCA). The challenge is identifying unique gate-to-LCA routes efficiently without recomputing paths for every query.
Approach 1: Brute Force DFS per Query (O(n) per query time, O(n) space)
For every query, run a DFS from each gate node up toward the root and explicitly track the path until the LCA is found. Store visited nodes in a set to avoid double counting. This works because trees guarantee a single path between nodes, but repeatedly traversing the tree makes it expensive when queries are large. This approach is mainly useful for validating correctness or when the number of queries is very small. Traversal can be implemented using standard DFS on the tree.
Approach 2: Path Reconstruction Using Parent Pointers (O(h) per query time, O(n) space)
Precompute each node's parent and depth using a single DFS. For a query, walk both nodes upward until they meet at the LCA. While climbing, track which gates appear on the path using a hash set or frequency map. Because each step moves toward the root, the traversal cost depends on the tree height h. This reduces repeated full traversals but still becomes slow on skewed trees where h ≈ n. It demonstrates how path intersection naturally reveals the LCA.
Approach 3: Binary Lifting LCA with Prefix Path State (O((n + q) log n) time, O(n log n) space)
Preprocess the tree using binary lifting to answer LCA queries in O(log n). During the initial DFS, maintain prefix information along the root-to-node path—such as counts, bitmasks, or hash signatures representing which gates appear. For a query, compute the LCA using the binary lifting table. The distinct path contribution from each node can be derived using prefix values from the two nodes and subtracting the prefix of the LCA's parent. This transforms repeated path exploration into constant-time prefix arithmetic after the LCA lookup.
Recommended for interviews: The binary lifting + prefix state approach is what most interviewers expect for a hard tree problem. The brute-force DFS shows you understand path structure in trees, but the optimized solution proves you can combine preprocessing, prefix aggregation, and LCA queries to handle large inputs efficiently.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS per Query | O(n) per query | O(n) | Small trees or very few queries where simplicity matters |
| Parent Pointer Path Reconstruction | O(h) per query | O(n) | Moderate constraints when tree height is small |
| Binary Lifting + Prefix Path Tracking | O((n + q) log n) | O(n log n) | Large inputs with many queries; standard optimal solution |
Practice Distinct Gate Paths to LCA with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor