시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 128 MB 56 6 (11%) 4
문제
시간 제한 1초, 메모리 제한 128MB Leonardo 시대에 가장 유명한 어린이용 게임은 "구슬과 줄"이었다. 당연하게도 이것은 구슬과 줄을 이용하는 게임이다. 줄은 빨간색이거나 파란색이고 구슬은 1번부터 n번까지 번호가 매겨져 있다. 게임을 하나의 구슬을 가지고 시작한다. 이제 아래와 같은 과정을 통해 새로운 구슬을 줄을 이용해서 더해나갈 수 있다. ``` Append(w, v): 새로운 w번 구슬을 기존의 v번 구슬에 빨간 줄을 이용해서 더한다 Insert(w, u, v): 새로운 w번 구슬이 기존에 빨간 줄로 이어진 u, v번 구슬 사이에 들어가며 u와 v사이의 빨간 줄은 제거되며 w와 u, v사이는 파란 줄로 이어준다. 즉 u와 v 사이를 잇는 빨간줄이 u과 w, w와 v 사이를 잇는 두 개의 파란줄로 교체된다. ``` 모든 줄(빨강, 파랑 모두)들은 길이를 가지고 있다. 게임이 끝나면 파란색 줄(빨간색 줄은 고려하지 않음)의 길이만 합산하여 이것을 최종 점수라고 부른다. 구슬과 줄 게임이 종료된 최종 상태가 주어진다. 상태를 보면 어떻게 구슬이 연결되어있고 각 줄들의 길이는 주어지지만 줄의 색은 주어지지 않는다. 주어진 상태에서 가능한 최대 점수를 계산하라. 더 정확하게는 주어진 상태처럼 끝나게 되는 구슬과 줄 게임 중에 가장 최종 점수(파란색 줄 길이의 합)가 큰 경우를 찾아서 그 값을 출력해야 한다.
입력
첫째 줄에 양의 정수 $n$ ($1$번부터 $n$번까지 있는 구슬의 개수) 이 주어진다. 다음 $n-1$개의 줄에는 각각 3개의 정수가 $a_i, b_i(1 ≤ a_i < b_i ≤ n)$과 $1 ≤ c_i ≤ 10000$이 주어진다 (두 구슬 $a_i, b_i$가 $c_i$만큼의 길이의 줄로 연결되어 있다.)
출력
첫째 줄에 최종 점수의 최대값을 출력한다.
힌트
#### 예제 입력 1 ``` 5 1 2 10 1 3 40 1 4 15 1 5 20 ``` #### 예제 출력 1 ``` 60 ``` #### 예제 입력 2 ``` 10 4 10 2 1 2 21 1 3 13 6 7 1 7 9 5 2 4 3 2 5 8 1 6 55 6 8 34 ``` #### 예제 출력 2 ``` 140 ``` #### 참고 예제 1에서 최종 점수 60은 3번 구슬로 시작하여 아래와 같이 만들어질 수 있다. ``` 5번 구슬을 3번 구슬에 더한다 (줄의 길이는 상관없다) 1번 구슬을 3, 5번 구슬 사이에 넣는다 (길이가 40, 20인 줄을 사용) 2번 구슬을 1번 구슬에 길이 10짜리 줄을 사용해서 더한다. 4번 구슬을 1번 구슬에 길이 15짜리 줄을 사용해서 더한다. ``` 이렇게 하면 아래 그림과 같은 상태가 되고 색을 제외하고 이와 같은 최종 상태를 가지며 더 큰 최종 점수를 가지는 상태는 존재하지 않는다. 예제 2에서는 아래와 같은 그림으로 만들 수 있고 이 경우에 최종 점수는 140이 된다. #### 점수 아래 4개의 서브태스크로 점수가 매겨진다. - 서브태스크 1 (13점) : $1 ≤ n ≤ 10$ - 서브태스크 2 (15점) : $1 ≤ n ≤ 200$ - 서브태스크 3 (29점) : $1 ≤ n ≤ 10000$ - 서브태스크 4 (43점) : $1 ≤ n ≤ 200000$