꽤나 다양한 것들을 알아야 풀 수 있는 문제입니다.
선수 지식은 아래와 같습니다.

• DFS 또는 BFS
• 그래프
• 트리
• 중간값

위와 같습니다. 모르는 것이 존재한다면, 고난의 길로 진입하오니 문제 풀이전에
한 번 학습해보시는 것을 추천드립니다. 아마 코딩 시작부터 레벨4를 풀려고 시도하는 사람은 없겠지만,
대부분은 중간값을 제외한 상단3개의 선수지식들을 잘 이해하고 있을겁니다.

먼저 중간값의 정의를 알아야합니다.
여기서 오해할만한 부분이 발생하는데, 중간값과 평균값은 엄연하게 다릅니다.
평균값은 데이터를 모두 더한 후에 데이터의 수만큼 나누어 준 값이지만,
중간값은 데이터를 오름차순으로 나열했을 경우, 가운데에 존재하는 값 그 자체를 의미합니다.
문제의 예시가 좀 숫자가 낮아서 답이 3값의 평균이라고 오해할 요소가 존재합니다.

만약 (1, 7, 100) 이라는 값이 존재한다면, 중간값은 3개의 값을 오름차순으로 나열한 값 중의 가운데의 값
7이 중간값이 됨을 알 수 있습니다.

문제의 그래프는 항상 트리 형태로 제공된다고 되어있습니다.
그렇기에 이 문제는 트리 형태의 그래프이기에 구할 수 있는 문제라는 것을 유추해볼 수 있습니다.
트리의 특징을 알아봅시다.

트리의 특징

• 트리는 비순환 그래프이다.
• 두 정점간의 거리는 항상 최소거리임을 보장한다.(두 정점 사이의 길은 하나만 존재함)

위의 2가지가 트리의 대표적인 특징입니다. 트리는 순환하지 않는 그래프입니다. 부모와 자식과 같은 형태로
이루어졌습니다. 비순환 그래프는 모든 정점에 대해서 반드시 길이 하나임을 보장합니다.
즉, 어떤 정점으로 부터 그래프가 이어진다고 가정했을 때, 역으로 돌아가지 않는 이상 절대로 자기 자신을 만날 수 없는
구조입니다. 그렇기에 임의의 두 정점간의 길은 하나로 유일하며, 그 거리가 항상 최소임을 보장합니다.
그렇기에 어떤 트리에서 A, B, C 정점을 지정하였을 때, A-B, B-C, C-A의 거리의 중간값이 최댓값이 되게하는 값을
쉽게 찾을 수 있습니다. 왜 그런지는 중간값의 특징을 살펴보면 알 수 있습니다.

1~10의 값이 존재할 경우, 해당 숫자에서 임의의 숫자 3개를 뽑았을 때, 중간값을 최대로 만들고 싶을 경우,
그 중간값은 무엇이 되겠는가?

답은 간단합니다. 중간값은 항상 시작과 끝이 존재해야합니다. 그렇기에 1, 10을 양 끝단을 두고 그 사이에서 가장 큰 수를
찾는다면 최대화 시킬 수 있는 중간값은 9밖에 존재하지 않습니다.
그렇다면, 이번에 배열에서 값을 3개 선택하여 중간값을 구해봅시다.

[1, 4, 5, 9, 9]

위와 같은 배열에서 값을 3개 고른다고 할경우, 중간값은 얼마인가요? 그렇죠. 바로 9입니다.
중간값은 중복된 숫자가 있을 경우, 최대에 해당되는 값이 중간값이 될 수 있습니다.
이로써 알 수 있는 사실은 트리의 최대거리를 계산하여, 최대거리의 나올 수 있는 경우의 수가 적어도 2개이상 존재할 경우.
해당 트리에서 나오는 중간값의 최대는 트리의 최대거리임을 알 수 있습니다.

여기서 왜 트리의 최대거리가 나오는지를 알아야 합니다.
우리는 정점 3개 A, B, C를 뽑아서 A-B, B-C, C-A 의 중간값이 최대가 되는 중간값을 알고 싶은겁니다.
중간값을 최대화 한다는 의미에서 단순히 보자면, 3개중에 2개만 신경써도 된다는 것을 알 수 있습니다.
A-B, B-C 가 최대가 되도록 하든가, B-C, C-A, 등이 최대가 되도록하는 거리를 알기만 하면 중간값은 둘 거리 중 작은 거리가
된다는 것을 알 수 있습니다. 어차피 두 개의 거리를 최대화 시켰다면, 남은 거리는 중간값의 이하이므로 무시해도 됩니다.
만약 남은거리가 최대화된 두 거리보다 크다면, 그건 최대화 시킨 두거리가 최대화 되지 않았음을 의미합니다.
트리에서의 두 정점의 거리는 항상 최소거리를 보장합니다. 그렇기에 반드시 두 정점의 거리가 최대가 되는 거리가 존재합니다.

제일 끝 정점 A에서, 가장 먼 정점 B가 존재한다고 가정합니다.
그런데, B와 같은 거리만큼 C정점또한 A에서 떨어진 정점이라고 합시다.
A-B, A-C가 트리에서 가질 수 있는 최대의 값을 가지므로, 두 정점 간의 거리가 정답이 됩니다.
최댓값을 2개 만들 수 있는 경우, 최댓값이 중간값이고 그 때의 중간값이 최댓값이라는 것을 알 수 있습니다.

만약에, 제일 끝 정점 A에서, 가장 먼 정점 B가 유일하게 하나만 존재한다고 가정합니다.
그럴 경우는 중간값이 얼마일까요? 눈치가 빠르면 쉽게 알겁니다.
최대값이 하나만 가지므로, 최대값을 가지는 정점보다 하나 아랫단계에 정점C라고 두면 정점C가 중간값이 됩니다.
최대거리가 하나만 존재하므로, 중간값의 최댓값은 항상 정해져있습니다.
그렇게 된다면, 그 다음으로 최대가 될 수 있는 정점을 C로 두어 중간값으로 지정해야합니다.
그런 경우, A-B가 최댓값이 되고, A-C의 값이 중간값이 됨을 알 수 있습니다. 나머지 B-C는 트리의 최대거리가 유일하므로,
항상 중간값인 A-C 거리의 이하임을 보장 할 수 있습니다.
해당 경우에는 중간값이 트리의 최대 거리에서 1을 뺀 값이 정답이 됩니다.

코드의 관점으로 해설해보겠습니다.
먼저, edge를 통해 간선정보를 확인하여, 양방향 그래프를 형성합니다.
다음으로 BFS나 DFS 탐색기법을 통해 트리의 제일 종단지점을 탐색합니다.
트리의 종단 지점이 여러개가 발생하므로, 임의의 지점 하나를 반환하도록 합니다.
여기서 거리 탐색전에 트리의 종단 지점을 찾는 이유는 트리는 어떤 정점을 기준으로 부모로 잡느냐에 따라
트리의 최대거리인 깊이가 변합니다. 이해가 안가신다면, 문제의 예시 트리를 보고 각 정점이 부모가 됨에 따라
달라지는 트리의 깊이를 확인하는 것도 좋은방법입니다.
트리의 종단지점은 그래프가 역으로 돌아가는 방법 말고는 더 이상 갈 방법이 없는 부분의 정점을 의미합니다.
트리는 비순환 그래프이므로 항상 종단 지점이 발생함을 보장합니다.

종단 지점을 구하였다면, 종단지점에서 부터 가장 먼 정점을 탐색합니다.
이 때, 탐색된 가장 먼 정점들의 중 임의의 정점 번호, 탐색된 최대 거리, 탐색된 정점들의 개수를 반홥니다.
탐색된 정점의 수가 2개 이상 존재할 경우, A-B와 A-C가 최대임을 보장하므로 트리의 최대 거리인
탐색된 최대 거리를 답으로써 리턴해줍니다.

아닐 경우, 다시 한 번 아까 구한 가장 먼 정점에서 다시 탐색을 시도합니다.
이제 의문이 들겁니다. 아까 종단구간에서 가장 먼 정점을 탐색하지 않았느냐? 왜 다시 탐색을 수행하는가?
당연히 의문이다. 나도 처음엔 그랬다.
그 이유는 탐색을 최대한 적은 횟수로 하기 위해서 그런 것이다.
원래는, 처음에 종단 정점에서 가장 먼 정점을 탐색하였다. 그렇지만, 사실 종단 정점은 하나가 아니라,
여러개가 존재한다. 임의의 종단 정점에서 가장 먼 거리의 정점을 구해내고, 그 개수도 구했다고 하더라도.
다른 임의의 종단 정점에서도 가장 먼거리를 계산하였을 겅우, 같은 최대 거리를 가진 정점을 탐색할 수 있기 때문이다.
그렇기 때문에, 한 번더 탐색하여, 역으로 뒤집어서 탐색할 경우, 최대거리가 보장된 정점으로 부터,
다시 다른 종단 정점들을 향해 거리를 탐색할 경우, 한 개가 아니라 2개 이상이 나올 가능성이 존재한다.
그렇기에 이미 구해진 최대 정점에서 다시 한 번 탐색을 시도하여, 최대거리를 가지는 정점의 개수를 탐색한다.

답은 항상 트리의 최대 깊이거나, 그보다 하나 낮은 수임을 알 수 있다.
트리의 최대 깊이 - 1 이 답이 되는 경우는 2번의 탐색에도 최대 거리의 수가 유일하게 나올 때이다.

answer = tree_depth or tree_depth-1