아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

트리의 기둥과 가지

면접 대비

시간 제한2.5초메모리 제한1024 MB

요약
루트가 있는 가중 트리에서 루트부터 내려가며 자식이 2개 이상인 첫 노드(또는 유일한 잎)인 기가 노드를 찾고, 루트에서 기가 노드까지의 줄기 길이와 기가 노드에서 잎까지의 가장 긴 가지 길이를 출력한다.
난이도

보통10점 중 5점

유형
트리, DFS, 구현, 재귀
정답자
아직 제출이 없습니다

문제

시청 공무원 마이크로는 과장으로부터 시에 있는 나무의 기둥의 길이와 가장 긴 가지의 길이를 파악하라는 업무 지시를 받았다.

마이크로는 ICPC Sinchon Winter Algorithm Camp에서 배운 트리 자료 구조를 이용하면 이 작업을 좀 더 수월하게 할 수 있으리라 판단했다.

마이크로는 트리의 기둥과 가지를 분류하기 위해 기가 노드를 추가로 정의하였다.

기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 22개 이상인 노드다. 기둥-가지를 줄여 기가 노드라 이름 붙였다. 위 그림에서 기가 노드는 44번 노드다.

단, 위 그림과 같이 리프 노드가 단 11개인 경우 리프 노드가 동시에 기가 노드가 된다.

또한, 위 그림과 같이 루트 노드가 동시에 기가 노드인 경우도 가능하다.

  • 트리의 기둥은 루트 노드에서부터 기가 노드까지다. 위 그림에서 기둥은 1−2−3−41-2-3-4 이다.
    기둥의 길이는 기둥의 간선 길이의 합인 1+2+3=61 + 2 + 3 = 6 이 된다.
  • 트리의 가지는 기가 노드에서부터 임의의 리프 노드까지다. 위 그림에서 가지는 4−5−6−74-5-6-7, 4−5−84-5-8, 4−94-9, 4−10−114-10-11, 4−10−124-10-12 총 55개가 있다.
    가지의 길이는 가지의 간선 길이의 합이다. 다행히도 가장 긴 가지의 길이 하나만 기재하면 된다. 4−10−124-10-12 가지가 간선 길이의 합 3+3=63 + 3 = 6 으로 가장 긴 가지이다.

마이크로는 시의 나무를 트리 자료 구조로 옮겼다. 그런데 과장이 마이크로에게 또 다른 업무를 지시했다! 너무 바쁜 마이크로를 대신해 트리의 기둥과 가장 긴 가지의 길이를 측정하자.

입력

첫 번째 줄에는 노드의 개수 NN(1≤N≤200 0001 \le N \le 200\,000)과 루트 노드의 번호 RR(1≤R≤N1 \le R \le N)이 주어진다.

이후 N−1N-1개의 줄에 세 개의 정수 aa, bb, dd(1≤a,b≤N1 \le a, b \le N, a≠ba \ne b)가 주어진다. 이는 aa번 노드와 bb번 노드가 연결되어있으며 이 간선의 길이가 dd(1≤d≤1 0001 \le d \le 1\,000)임을 의미한다. 노드는 11번부터 NN번까지 정수 번호가 매겨져 있으며 같은 간선은 여러 번 주어지지 않는다.

트리가 아닌 그래프는 입력으로 주어지지 않는다.

출력

나무의 기둥의 길이와 가장 긴 가지의 길이를 출력한다.

예제4

  1. 예제 1

    입력
    12 1
1 2 1
2 3 2
3 4 3
4 5 1
5 6 2
6 7 1
5 8 1
4 9 2
4 10 3
10 11 1
10 12 3
    예상 출력
    6 6

  2. 예제 2

    입력
    9 1
1 2 5
2 3 4
3 4 2
2 5 5
1 6 8
1 7 6
7 8 7
7 9 1
    예상 출력
    0 13

  3. 예제 3

    입력
    4 1
1 2 100
2 3 10
3 4 1
    예상 출력
    111 0

  4. 예제 4

    입력
    1 1
    예상 출력
    0 0