У меня есть корень дерева без корней и данные запросов в форме u и v. Я должен вычислять запросы пути от u до v, например, давать сумму частот весов вдоль пути. Я попытался найти lca в некорневом дереве, но это ни к чему не привело, так как lca вычисляется со ссылкой на узел. Как мне go включить для решения запросов пути в целом, работающих с весами на этом пути в некорневом дереве?
Выберите любую вершину как root.
root
Сохранить расстояние вершины от root для всех вершин.
d[x] = расстояние x от root
d[x]
x
для расстояние (a, b) = расстояние (lca, a) + расстояние (lca, b)
a
b
lca
(d[b] - d[lca(a, b)]) + (d[a] - d[lca(a, b)])