트리의 모든 노드 쌍 사이의 거리

Question

주어진 트리. 크기가 n * n 인 2D 행렬을 사용하지 않고 트리에서 모든 노드 쌍 사이의 거리를 찾는 방법. 나는 O (n^2)의 복잡성에 대한 해결책을 안다.

Answer 1

이미 주석에서 언급했듯이 트리의 v1,v2 모든 정점 쌍에 대해 출력이 (v1,v2,distance)이어야한다고 가정하십시오. n*(n-1) 쌍의 정점이 있습니다. n*(n-1)은 O(n^2)에 있으며 출력 크기는 이므로 O(n^2)을 더 잘 수행 할 수 없으므로 큰 O 표기법으로 알고리즘이 최적입니다.

Answer 2

빠른 사전 처리로 형식이 distance(u, v) 인 빠른 질의에 응답하려면 LCA을 사용할 수 있습니다. 루트가있는 트리의 두 꼭지점의 LCA 또는 가장 낮은 공통 조상은 둘 모두의 조상이고 모든 공통 조상 중에서 가장 낮은 정점입니다. n log n 사전 처리 시간을 사용하여 로그 시간에 LCA(u, v)을 찾는 매우 복잡한 알고리즘은 없습니다. 필요한 경우 설명 할 수 있습니다.

따라서 다음과 같이 문제가 해결 될 수 있습니다. 먼저, 나무의 뿌리를 고친다. 그런 다음 위에서 언급 한 전처리 과정을 통해 LCA를 찾을 수 있습니다. 그런 다음 h[v]이 v에서 루트까지의 거리 (모든 정점에 대해 선형 시간으로 미리 계산 될 수 있음)를 가정하면 distance(u, v) = h[u] + h[v] - 2 * h[LCA(u, v)]입니다.