Найти общее кратчайшее расстояние между несколькими путями в дереве

Question

Учитывая ненаправленное взвешенное дерево (N-узел, двунаправленный край N-1, не обязательно двоичное дерево). Ввод будет простым путем (от начального узла до самого низкого общего предка до конечного узла) между некоторыми узлами, например 1-> 4, 2-> 10. Найдите кратчайший общий (принадлежащий) к всем заданным путям.

Answer 1

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

i = 0 

// set up counts 
for each path p 
    for each node n on path 
    if n.count != i // early path stop condition, past common ancestor 
     break // go to next path 
    n.count++ 
    i++ 

current = root 
shortestEdge = null 

// find shortest edge 
while true 
    for each child c of current 
    if c.count == pathCount 
     shortestEdge = shortest(shortestEdge, edge(current, c)) 
     current = c 
     break // out of for-loop 
    else 
     stop // stop while-loop