Cycle Length Queries in a Tree
You are given an integer n. There is a complete binary tree with 2^n - 1 nodes. The root of that tree is the node with the value 1, and every node with a value val in the range [1, 2^n - 1 - 1] has two children where:
- The left node has the value
2 * val. - The right node has the value
2 * val + 1.
You are also given a 2D integer array queries of length m, where queries[i] = [ai, bi]. For each query, solve the following problem:
- Add an edge between the nodes with values
aiandbi. - Find the length of the cycle in the graph.
- Remove the added edge between nodes with values
aiandbi.
Note that:
- A cycle is a path that starts and ends at the same node, and each edge in the path is visited only once.
- The length of a cycle is the number of edges visited in the cycle.
- There could be multiple edges between two nodes in the tree after adding the edge of the query.
Return an array answer of length m where answer[i] is the answer to the i^th query.
Example 1
Input
n = 3, queries = [[5,3],[4,7],[2,3]]Output
[4,5,3]After adding each queried edge, the resulting cycle lengths are 4, 5, and 3 respectively.
Example 2
Input
n = 2, queries = [[1,2]]Output
[2]After adding the edge between nodes 1 and 2, the graph contains a cycle of length 2.
Constraints
- 2 <= n <= 30
- m == queries.length
- 1 <= m <= 10^5
- queries[i].length == 2
- 1 <= ai, bi <= 2^n - 1
- ai != bi