[Tree] 중앙 정점

트리의 중앙 정점

트리에서 다른 모든 정점까지의 거리의 합이 최소가 되는 정점

중앙 정점을 구하기 위해서는 트리의 임의의 정점에서 다른 모든 정점까지의 거리의 합을 알아야 한다.

i에서 i의 서브트리에 속하는 모든 정점들까지의 거리의 합을 vSum[i],
i에서 i의 서브트리에 속하지 않는 모든 정점들까지의 거리의 합을 rSum[i] 이라 할 때,

정점 i에서 다른 모든 정점까지의 거리의 합은 vSum[i] + rSum[i]로 나타낼 수 있다.

1. i에서 i의 서브트리에 속하는 모든 정점들까지의 거리의 합 (vSum[i])

vSum[i]을 구하기 위해서는 i의 직계 자손들을 서브트리의 루트로 하는 정점들의 vSum[i의 직계자손]와 그 서브트리에 속하는 총 정점의 수(vCount[i의 직계자손])가 필요하다.

i와 i의 직계자손의 거리가 d라고 가정하면 vSum[i]는 아래와 같이 표현할 수 있다.

vSum[i] = vSum[i의 직계자손] + (vCount[i의 직계자손] * d)

2. i에서 i의 서브트리에 속하지 않는 모든 정점들까지의 거리의 합 (rSum[i])

rSum[i]는 1번을 계산하면서 구해둔 vSum과 vCount를 활용해야 하며 아래 세 가지 경우를 합산하여 구할 수 있다.

(1) i의 부모노드에 속하지 않는 모든 정점들까지의 거리의 합 rSum[i의 parent]
rSum[i의 parent]는 root부터 차례로 구하기 때문에 i에 대한 rSum을 구할때는 구해져 있다. (root일 때는 rSum[root]=0, root 정점을 루트로 하는 서브트리에 속하지 않는 정점은 없다.)

(2) i의 부모노드에서 i의 부모노드의 서브트리에 속하면서 i의 서브트리에는 속하지 않는 정점들까지의 거리의 합
vSum[i의 parent] - (vSum[i] + (vCount[i] * d))  ( * d는 i와 i의 parent 까지의 거리)

(3) i의 서브트리에 속하지 않는 정점들이 i의 부모노드와 i 사이의 간선을 타고 들어오는 거리의 합
(vCount(root) - vCount[i]) * d

rSum[i] = rSum[i의 parent] + vSum[i의 parent] - (vSum[i] + (vCount[i] * d)) + (vCount(root) - vCount[i]) * d