LCA с использованием разреженной матрицы за время O (logn)
[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)» мы должны прыгнуть?
Решение
Во-первых, этот ответ не объясняет фрагмент, которым вы поделились.
Я действительно не понял эту часть кода. Я не уверен, что код там глючит или нет, потому что это кажется неправильным. Я могу поделиться своей функцией в этой части, надеюсь, вам может быть немного легче понять. Я добавил комментарий, чтобы облегчить ваше понимание.
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];
}
Другие решения
Других решений пока нет …