시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2.5 초 (추가 시간 없음) | 1024 MB | 2265 | 741 | 572 | 32.280% |
시청 공무원 마이크로는 과장으로부터 시에 있는 나무의 기둥의 길이와 가장 긴 가지의 길이를 파악하라는 업무 지시를 받았다.
마이크로는 ICPC Sinchon Winter Algorithm Camp에서 배운 트리 자료 구조를 이용하면 이 작업을 좀 더 수월하게 할 수 있으리라 판단했다.
마이크로는 트리의 기둥과 가지를 분류하기 위해 기가 노드를 추가로 정의하였다.
기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 $2$개 이상인 노드다. 기둥-가지를 줄여 기가 노드라 이름 붙였다. 위 그림에서 기가 노드는 $4$번 노드다.
단, 위 그림과 같이 리프 노드가 단 $1$개인 경우 리프 노드가 동시에 기가 노드가 된다.
또한, 위 그림과 같이 루트 노드가 동시에 기가 노드인 경우도 가능하다.
마이크로는 시의 나무를 트리 자료 구조로 옮겼다. 그런데 과장이 마이크로에게 또 다른 업무를 지시했다! 너무 바쁜 마이크로를 대신해 트리의 기둥과 가장 긴 가지의 길이를 측정하자.
첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다.
이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 노드와 $b$번 노드가 연결되어있으며 이 간선의 길이가 $d$($1 \le d \le 1\,000$)임을 의미한다. 노드는 $1$번부터 $N$번까지 정수 번호가 매겨져 있으며 같은 간선은 여러 번 주어지지 않는다.
트리가 아닌 그래프는 입력으로 주어지지 않는다.
나무의 기둥의 길이와 가장 긴 가지의 길이를 출력한다.
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
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
4 1 1 2 100 2 3 10 3 4 1
111 0
1 1
0 0
Camp > ICPC Sinchon Algorithm Camp > 2021 ICPC Sinchon Winter Algorithm Camp Contest > 초급 E번