2509. Cycle Length Queries in a Tree

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:

1. Add an edge between the nodes with values ai and bi.
2. Find the length of the cycle in the graph.
3. Remove the added edge between nodes with values ai and bi.

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.

class Solution {
    int find(int u) {
        int res = 0;
        while(u) {
            res += 1;
            u /= 2;
        }
        return res - 1;
    }
    int lcs(int u, int v) {
        string U = "", V = "";
        while(u) {
            U.push_back((u & 1) + '0');
            u /= 2;
        }
        while(v) {
            V.push_back((v & 1) + '0');
            v /= 2;
        }
        int res = 0;
        while(U.length() and V.length()) {
            if(U.back() != V.back()) break;
            res *= 2;
            if(U.back() == '1') res |= 1;
            U.pop_back();
            V.pop_back();
        }
        return res;
    }
public:
    vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
        vector<int> res;
        for(auto& q : queries) {
            int u = q[0], v = q[1];
            res.push_back(find(u) + find(v) + 1 - 2 * find(lcs(u,v)));
        }
        return res;
    }
};