사실 음수 가중치가 있는 트리에서 지름을 구하라는 문제를 접한적이 없어서, 실제로 구현해본적도 없다.
트리의 중심과 반지름을 구하기
먼저 알고 있어야 할 성질은, 트리의 반지름은 항상 트리의 지름에 포함된다는 것이다.
dist(u,v)가 트리의 지름이라면, u→v 경로 안의 노드들 중에 트리의 중심 r이 존재하고, 트리의 반지름은 max(dist(r,u), dist(r,v))가 된다.
트리의 중심이 여러개여도 마찬가지. 모두 다 u→v 경로 안에 들어간다.
거리가 지름과 같은 노드쌍이 여러개일 수도 있다. 그러한 경로들이 모두 겹치는 구간 안에 트리의 중심이 존재한다.
이제 저 성질을 이용해서 u→v 경로 안의 노드들 중에서 중심과 반지름을 구하면 된다.
dist(u,v)가 트리의 지름일때, 반지름을 구하기 위해서는 dist(u,X)과 dist(v,X)가 필요한데, 지름을 구하는 과정에서 이미 dist(u, X)는 모두 구했을것이고, dist(v,X) = dist(u,v) - dist(u,X) 이므로 따로 구할 필요가 없다.
각 노드의 이심률과 가장 멀리 떨어져있는 노드를 구하기
u의 이심률은 u에서 가장 멀리 떨어져있는 노드까지의 거리이다. (위에도 적었지만, 잘 안쓰는 용어이다보니 까먹을까 봐 다시 한번 적는다)
트리의 지름을 찾을 때 사용한 성질인, 임의의 노드에서 가장 멀리 떨어진 노드는, 그래프의 지름을 이루는 양 끝 노드들 중 하나가 된다를 이용하면 방법은 직관적으로 나온다.
트리의 지름을 찾고 → 트리의 지름을 이루는 양 끝 노드 u, v로부터 각각 BFS를 돌려서 각 노드까지의 거리를 구해둔다.
dist(u, X)는 트리의 지름을 계산하는 과정에서 이미 구했을 것이므로, dist(v, X)만 추가로 구하면 된다
어떤 노드 w에서 가장 먼 노드는, dist(u, w)과 dist(v, w) 중 값이 큰 쪽에 해당되는 노드이다.
식을 조금 바꿔서 정리하면, w의 이심률은 {w에서 중심까지의 거리} + {반지름} 이 된다고도 쓸 수 있다.