LCA с использованием разреженной матрицы за время O(logn)

Question

[1]: https://www.geeksforgeeks.org/lca-for-general-or-n-ary-trees-sparse-matrix-dp-approach-onlogn-ologn/

for (int i=0; i<level; i++) 
    if ((diff>>i)&1) 
        v = parent[v][i];

В приведенном выше коде он переходит только к 2-му родительскому элементу, когда "(diff>>i)" нечетно. Почему это так? Как мы поняли, что только в случае нечетного "(diff>>i)" мы должны прыгнуть?

Answer 1

Во-первых, этот ответ не объясняет фрагмент, которым вы поделились.

Я действительно не понял эту часть кода. Я не уверен, что код там глючит или нет, потому что это кажется неправильным. Я могу поделиться своей функцией в этой части, надеюсь, вам может быть немного легче понять. Я добавил комментарий, чтобы облегчить ваше понимание.

int lcaQuery(int p, int q) {
    if(depth[p] < depth[q]) {
        swap(p, q);
    }

    // uplifting p at the same level/height of q
    for(int i = level - 1; i >= 0; i--) {
        if (depth[p] - (1 << i) >= depth[q]) {
            p = parent[p][i];
        }
    }

    // if already catch q, this is the LCA
    if (p == q) return p;

    // uplifting p and q until both of their parents are same and we reach the root
    for(int i = level - 1; i >= 0; i--) {
        if (parent[p][i] != -1 and parent[p][i] != parent[q][i]) {
            p = parent[p][i];
            q = parent[q][i];
        }
    }

    // since now both p and q are in the same level, return their parent
    return parent[p][0];
}