트리의 지름 (Diameter of tree)

트리에서 정점 두개를 잡고, 거리를 재본다.

n^2 쌍의 개수만큼 거리들이 나올텐데...

이 중 가장 거리가 긴 놈을 트리의 지름이라 부른다.

dfs 2번 돌려서 O(n)에 해결할 수 있다.

알고리즘 문제 해결 전략을 학교에 두고와서 (...) 인터넷에서 직접 찾아봤는데, 책에 있는 것보다 훨씬 우아하고 간결한 알고리즘이 존재했다!!

1. 아무 점이나 잡고(루트), 이 점에서 가장 거리가 먼 점 t를 잡는다.

2. t에서 가장 거리가 먼 점 u을 찾는다.

3. t - u가 트리의 지름. 끗

여기까지는 좋은데 이를 어떻게 증명하는지가 문제다.

인터넷에서 대강 주워들은 걸로 혼자 증명해 보려고 한다. 막가는 증명이니까 믿거나 말거나...

일단 루트에서 가장 거리가 먼 점 t가 만약 지름 안에 있다면, 그 점에서 가장 거리가 먼 점인 u까지의 경로가 지름이라는 것은 자명하다.

그래서 루트에서 가장 거리가 먼 점이 지름 안에 없다는 게 모순이라는 것을 보이면 된다. (귀류법)

루트를 1이라 두고 루트에서 가장 거리가 먼 임의의 점을 x라 두고 증명해보자.

Case 1 : t - u랑 1 - x랑 겹친다.

둘의 겹치는 부분을 p - q라고 하자.

그러면

(u) - (p) - (q) - (t)

_______|_____|______

______(1)___(x)______

OR

(t) - (p) - (q) - (u)

_______|_____|______

______(1)___(x)______

대략 이런 식으로... 트리가 생길 건데,

첫번째는 d(1,t) < d(1,x) 이다.

고로 d(q,t) < d(q,x) 이고, 이 때 d(u,t)보다 d(u,x)가 더 길어지니까 d(u,t)는 지름이 아니고 모순.

두번째에서도 d(1,t) < d(1,x) -> d(p,t) < d(p,x)이다.

그런데 d(p,u) < d(p,t)이다. 그래서 d(p,u) < d(p,t) < d(p,x)이다.

이 때 d(t,u) < d(t,x)이므로 역시 모순.

Case 2 : t - u랑 1 - x랑 안 겹친다.

1 - t와 t - u랑 겹치는 점을 p라고 두고, 1 - x와 1 - t랑 가장 마지막으로 겹치는 점 (LCA)를 q라고 두자.

(1) - (q) - (p) - (t)

_______|_____|______

______(x)___(u)______

역시...

이때 d(p,u) < d(p,t)이며 d(q,t) < d(q,x)이다.

d(q,u) < d(q,t) < d(q,x)인 것도 알 수 있다.

고로, d(t,x) > d(t,q) + d(q,u) > d(t,u) + 2 * d(p,q) 이다.

역시 d(t,u) 보다 긴 간선이 있으니 모순.

코드는 생략.