#2509
Cycle Length Queries in a Tree
expert · 1185 · lc hard +32 · verified · 60.2% accepted · 389 likes · top 59%
Description
Given a complete binary tree with 2n - 1 nodes (root = 1, children of node val are 2*val and 2*val+1) and a list of queries [ai, bi], for each query temporarily add an edge between nodes ai and bi, determine the length (number of edges) of the resulting cycle, then remove the added edge. Return the array of cycle lengths.
Example 1:
Input: n = 3, queries = [[5,3],[4,7],[2,3]]
Output: [4,5,3]
Explanation: The diagrams above show the tree of 23 - 1 nodes. Nodes colored in red describe the nodes in the cycle after adding the edge.
- After adding the edge between nodes 3 and 5, the graph contains a cycle of nodes [5,2,1,3]. Thus answer to the first query is 4. We delete the added edge and process the next query.
- After adding the edge between nodes 4 and 7, the graph contains a cycle of nodes [4,2,1,3,7]. Thus answer to the second query is 5. We delete the added edge and process the next query.
- After adding the edge between nodes 2 and 3, the graph contains a cycle of nodes [2,1,3]. Thus answer to the third query is 3. We delete the added edge.
Example 2:
Input: n = 2, queries = [[1,2]]
Output: [2]
Explanation: The diagram above shows the tree of 22 - 1 nodes. Nodes colored in red describe the nodes in the cycle after adding the edge.
- After adding the edge between nodes 1 and 2, the graph contains a cycle of nodes [2,1]. Thus answer for the first query is 2. We delete the added edge.
Code
1
2
3