You are given an integer n
. There is a complete binary tree with 2n - 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, 2n - 1 - 1]
has two children where:
- The left node has the value
2 * val
, and - 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
ai
andbi
. - Find the length of the cycle in the graph.
- Remove the added edge between nodes with values
ai
andbi
.
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 ith
query.
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.
Constraints:
2 <= n <= 30
m == queries.length
1 <= m <= 105
queries[i].length == 2
1 <= ai, bi <= 2n - 1
ai != bi
Companies: Arcesium
Related Topics:
Tree, Binary Tree
Similar Questions:
- Populating Next Right Pointers in Each Node (Medium)
- Lowest Common Ancestor of a Binary Tree (Medium)
- Path In Zigzag Labelled Binary Tree (Medium)
- Find the lowest common ancestors
C
ofA
andB
{distance from A to C} + {distance from B to C} + 1
// OJ: https://leetcode.com/problems/cycle-length-queries-in-a-tree
// Author: github.com/lzl124631x
// Time: O(QlogN)
// Space: O(logN)
class Solution {
public:
vector<int> cycleLengthQueries(int n, vector<vector<int>>& Q) {
vector<int> ans;
auto getPath = [&](int n) { // Returns the path from root to node n.
vector<int> ans;
while (n) {
ans.push_back(n);
n /= 2;
}
reverse(begin(ans), end(ans));
return ans;
};
for (auto &q : Q) {
int a = q[0], b = q[1], i = 0;
auto pa = getPath(a), pb = getPath(b);
for (; i < pa.size() && i < pb.size() && pa[i] == pb[i]; ++i);
ans.push_back(pa.size() + pb.size() - 2 * i + 1);
}
return ans;
}
};
// OJ: https://leetcode.com/problems/cycle-length-queries-in-a-tree
// Author: github.com/lzl124631x
// Time: O(QlogN)
// Space: O(1)
class Solution {
public:
vector<int> cycleLengthQueries(int n, vector<vector<int>>& Q) {
vector<int> ans;
for (auto &q : Q) {
int len = 1, a = q[0], b = q[1];
while (a != b) {
if (a > b) a /= 2;
else b /= 2;
++len;
}
ans.push_back(len);
}
return ans;
}
};