시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 2 2 2 100.000%

문제

아폴로니안 네트워크는 무방향 그래프로, 삼각형에서 시작하여 중간에 있는 삼각형을 3개의 작은 삼각형으로 재귀적으로 분할하는 방식으로 구성된다. 

가중치 있는 아폴로니안 네트워크에서, 가중치 합이 최대인 단순 경로의 가중치 합을 출력하라.

입력

첫 번째 줄에 정점의 개수 n이 주어진다. (3 ≤ n ≤ 250)

이후 3(n-2) 개의 줄에 간선의 정보 ai, bi, ci 가 주어진다. 해당 간선이 두 정점 ai, bi 를 ci의 가중치로 잇는다는 것이다. (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 106)

주어진 그래프는 아폴로니안 네트워크이다.

출력

가중치 합이 최대인 단순 경로의 가중치 합을 출력하라.

예제 입력 1

3
1 2 1
2 3 1
3 1 2

예제 출력 1

3

예제 입력 2

10
1 2 4
2 3 4
3 1 3
6 1 3
6 2 3
6 3 4
4 6 4
4 3 4
4 2 3
5 1 3
5 6 3
5 2 4
10 1 4
10 3 3
10 6 3
7 1 4
7 10 4
7 6 3
8 1 3
8 3 4
8 10 4
9 3 4
9 8 3
9 10 3

예제 출력 2

35

출처

  • 문제를 번역한 사람: koosaga