Определить расстояние между двумя случайными узлами в дереве

Question

Учитывая общее дерево, я хочу расстояние между двумя узлами v и w.

Википедия states the following:

Вычисление низких общих предков может быть полезным, например, как часть процедуры для определения расстояния между парами узлов в дереве: расстояние от v до ж может быть вычисляется как расстояние от корня до v, плюс расстояние от корня до w, минус в два раза больше расстояния от корня до самого низкого общего предка.

Скажем d(x) обозначает расстояние от узла x от корня, который мы установили в 1. d(x,y) обозначает расстояние между двумя вершинами x и y. lca(x,y) обозначает наименьший общий предок пары вершин x и y.

Таким образом, если у нас есть 4 и 8, lca(4,8) = 2 поэтому, согласно приведенному выше описанию, d(4,8) = d(4) + d(8) - 2 * d(lca(4,8)) = 2 + 3 - 2 * 1 = 3. Отлично, это сработало!

Однако дело было указано выше, кажется, не в состоянии для вершины пары (8,3) (lca(8,3) = 2) d(8,3) = d(8) + d(3) - 2 * d(2) = 3 + 1 - 2 * 1 = 2. Это неверно, однако, расстояние d(8,3) = 4, как можно видеть на графике. Кажется, что алгоритм терпит неудачу для всего, что пересекает определенный корень.

Что мне не хватает?

Answer 1

Вы пропустили это lca(8,3) = 1, а не = 2. Следовательно, d(1) == 0, который делает это:

d(8,3) = d(8) + d(3) - 2 * d(1) = 3 + 1 - 2 * 0 = 4 

Answer 2

Для соответствующего 2 узла, а именно один один справа, d(lca(8,2)) == 0, а не 1, как у вас в вашем выводе. Расстояние от корня - то есть lca в этом случае - само по себе равно нулю. Так

d(8,2) = d(8) + d(2) - 2 * d(lca(8,2)) = 3 + 1 - 2 * 0 = 4 

Тот факт, что у вас есть два узла, помеченных 2 вероятно запутанные вещи.

Edit: Сообщение было отредактировано так, что узел первоначально обозначенный 2 теперь называется 3. В этом случае вывод теперь правильно, но заявление

the distance d(8,2) = 4 as can be seen on the graph 

неверен, d (8 , 2) = 2.