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

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

0 голосов
/ 14 сентября 2018

[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)» мы должны прыгнуть?

1 Ответ

0 голосов
/ 14 сентября 2018

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

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

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];
}
...