====== 트리의 지름 ======

  * 참고 
    * [[https://00ad-8e71-00ff-055d.tistory.com/115]] 
    * [[https://codeforces.com/blog/entry/101271]]
  * 먼저 관련된 텀들을 정의해야 한다.
    * 트리뿐 아니라 일반 그래프에서도 똑같이 정의되는 텀들이다.
  * 노드 v의 이심률(eccentricity of v): v와 다른 노드들 까지의 거리중 가장 긴 거리. (=v에서 가장 멀리 떨어진 노드까지의 거리)
    * 그래프가 연결그래프가 아닌 경우에는, 모든 노드의 이심률이 무한대로 정의된다
  * 그래프의 지름(graph diameter): 이심률의 최댓값 (= 이심률이 최대인 노드에서의 이심률)
    * 그래프에서 가장 멀리 떨어저있는 두 노드 사이의 거리
  * 그래프의 반지름(graph radius): 이심률의 최솟값 (= 이심률이 최소인 노드에서의 이심률)
    * 그래프의 중심에서 가장 멀리 떨어진 노드까지의 거리
  * 그래프의 중심 (center of graph): 이심률이 그래프의 반지름과 같은 노드들 
    * 가장 멀리 떨어진 노드까지의 거리가 최소인 노드들
    * 그래프는 중심을 여러개 가질수도 있다.
    * 센트로이드(Centroid)와는 다른 개념이다!

===== 트리의 지름을 구하기 =====

==== 음수 가중치가 없는 경우 ====
  * 대부분의 여기에 해당한다.
  * 일반적으로는 두번의 DFS 로 구하는 방법이 가장 빠르고 간단하다.
  * 알고리즘은
    * 1. 임의의 노드에서 DFS를 돌려서 가장 멀리 떨어진 노드 a를 찾는다
    * 2. a에서 DFS를 돌려서 가장 멀리 떨어진 노드 b를 찾는다.
    * 3. dist(a,b)가 트리의 지름이 된다(!)
  * 시간복잡도는 O(n).
  * 증명은 위의 링크들을 참고하고.. 여기서 기억해야 될 특성은, 임의의 노드에서 가장 멀리 떨어진 노드는, 그래프의 지름을 이루는 두 노드들 중 하나가 된다는 것이다.

==== 음수 가중치가 있는 경우 ====
  * 트리에 음수 가중치가 있는 경우에는 위의 방법으로 불가능하다. 트리 DP를 사용해서 구할수 있다
  * 방법은 [[https://00ad-8e71-00ff-055d.tistory.com/115]]을 참고
  * 사실 음수 가중치가 있는 트리에서 지름을 구하라는 문제를 접한적이 없어서, 실제로 구현해본적도 없다.

===== 트리의 반지름을 구하기 =====
  * 먼저 알고 있어야 할 성질은, 트리의 반지름은 항상 트리의 지름에 포함된다는 것이다. 
    * 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) 이므로 따로 구할 필요가 없다.