트리의 여러 경로 사이에 공통 최단 에지 찾기

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