2509.查询树中环的长度

链接：2509.查询树中环的长度
难度：Hard
标签：树、数组、二叉树
简介：请你返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 个查询的结果。

题解 1 - cpp

• 编辑时间：2022-12-18
• 执行用时：324ms
• 内存消耗：95.9MB
• 编程语言：cpp
• 解法介绍：最近公共祖先。

struct Node{
    int v, p;
    unordered_set<int> l, r;
};
class Solution {
public:
    vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
        vector<int> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            ans[i] = query(n, queries[i]);
        }
        return ans;
    }
    int query(int n, vector<int> &q) {
        int n1 = q[0], n2 = q[1],
            l1 = getLevel(n1), l2 = getLevel(n2);
        if (l1 < l2) {
            swap(n1, n2);
            swap(l1, l2);
        }
        // cout << "n1 = " << n1 << ", l1 = " << l1 << ", n2 = " << n2 << ", l2 = " << l2 << endl;
        int ans = 0;
        while (l1 > l2) {
            n1 = getParent(n1);
            l1 = getLevel(n1);
            ans++;
        }
        while (n1 != n2) {
            ans += 2;
            n1 = getParent(n1);
            n2 = getParent(n2);
        }
        // cout << "n1 = " << n1 << ", l1 = " << l1 << ", n2 = " << n2 << ", l2 = " << l2 << endl;
        return ans + 1;
    }
    int comp(int n1, int n2) {
        return 0;
    }
    unordered_map<int, int> m;
    int getLevel(int val) {
        if (m.count(val)) return m[val];
        int i = 1, level = 0;
        while (i <= val) i *= 2, level++;
        return m[val] = level;
    }
    int getParent(int v) {
        if (v == 1) return v;
        return v / 2;
    }
};