Расстояние между двумя узлами в весовом дереве

Question

Мой вопрос очень прост.

Дается взвешенное дерево. Мы должны найти расстояние между двумя заданными узлами.

так как количество запросов очень велико (около 75000) каждый раз, когда время ожидания bfs истекает, поэтому я попробовал другой способ сделать это.

Мой алгоритм такой:

• Я запускал dfs из вершины 0 и вычислял расстояние от корня (0) до всех вершин примерно так

      depth[v]=depth[u]+w,where u is parent of v and w is weight b/w (u,v)
  

• Однажды я вычислил глубину всех узлов, используя dfs и 2^j-й родитель каждого узла (предположим, я знаю, как это сделать). Я рассчитал LCA для (u,v), запрошенного для каждого запроса.

• Затем я рассчитал расстояние, как это

      distance between (u,v)=depth[u]+depth[v]-2*depth[lca(u,v)] 
  

Но я не получаю верный вердикт, как ожидалось.Мой алгоритм правильный, или я что-то упускаю. Нужно руководство:)

Ps Incase кто-нибудь хочет увидеть мою реализацию - ссылка http://paste.ubuntu.com/13129038/

Answer 1

Ваш подход звучит разумно, но, глядя на связанный код, я предлагаю вам попробовать небольшой пример (например, с 3 узлами в дереве) и внимательно проверить содержимое родительского массива.

Насколько я вижу, единственные строки, изменяющие содержимое родительского массива:

memset(parent,-1,sizeof parent);

а также

parent[i][j]=parent[i-1][parent[i-1][j]]

поэтому я считаю, что содержание parent всегда будет равно -1.

Возможно, вам нужен базовый случай, устанавливающий parent[0][j], равный родителю j?

Кроме того, из кода не совсем ясно, используете ли вы значение глубины для подсчета количества ребер или сумму весов всех ребер. Для расчета расстояния вам понадобится сумма весов, но для работы алгоритма LCA вам может понадобиться счетчик ребер.