2509. Cycle Length Queries in a Tree Hard

1/**
2 * [2509] Cycle Length Queries in a Tree
3 *
4 * 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:
5 * 
6 * 	The left node has the value 2 * val, and
7 * 	The right node has the value 2 * val + 1.
8 * 
9 * You are also given a 2D integer array queries of length m, where queries[i] = [ai, bi]. For each query, solve the following problem:
10 * <ol>
11 * 	Add an edge between the nodes with values ai and bi.
12 * 	Find the length of the cycle in the graph.
13 * 	Remove the added edge between nodes with values ai and bi.
14 * </ol>
15 * Note that:
16 * 
17 * 	A cycle is a path that starts and ends at the same node, and each edge in the path is visited only once.
18 * 	The length of a cycle is the number of edges visited in the cycle.
19 * 	There could be multiple edges between two nodes in the tree after adding the edge of the query.
20 * 
21 * Return an array answer of length m where answer[i] is the answer to the i^th query.
22 *  
23 * <strong class="example">Example 1:
24 * <img alt="" src="https://assets.leetcode.com/uploads/2022/10/25/bexample1.png" style="width: 647px; height: 128px;" />
25 * Input: n = 3, queries = [[5,3],[4,7],[2,3]]
26 * Output: [4,5,3]
27 * Explanation: The diagrams above show the tree of 2^3 - 1 nodes. Nodes colored in red describe the nodes in the cycle after adding the edge.
28 * - 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.
29 * - 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.
30 * - 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.
31 * 
32 * <strong class="example">Example 2:
33 * <img alt="" src="https://assets.leetcode.com/uploads/2022/10/25/aexample2.png" style="width: 146px; height: 71px;" />
34 * Input: n = 2, queries = [[1,2]]
35 * Output: [2]
36 * Explanation: The diagram above shows the tree of 2^2 - 1 nodes. Nodes colored in red describe the nodes in the cycle after adding the edge.
37 * - 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.
38 * 
39 *  
40 * Constraints:
41 * 
42 * 	2 <= n <= 30
43 * 	m == queries.length
44 * 	1 <= m <= 10^5
45 * 	queries[i].length == 2
46 * 	1 <= ai, bi <= 2^n - 1
47 * 	ai != bi
48 * 
49 */
50pub struct Solution {}
51
52// problem: https://leetcode.com/problems/cycle-length-queries-in-a-tree/
53// discuss: https://leetcode.com/problems/cycle-length-queries-in-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57impl Solution {
58    pub fn cycle_length_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
59        vec![]
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_2509() {
71    }
72}
73