아폴로니안 네트워크

시간 제한3초메모리 제한512 MB

요약
가중치가 있는 아폴로니안 네트워크에서 간선 가중치 합이 최대인 단순 경로를 찾아 그 합을 출력한다.
난이도

보통10점 중 6점

유형
트리, 동적 계획법, DFS
정답자
아직 제출이 없습니다

문제

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

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

입력

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

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

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

출력

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

예제2

  1. 예제 1

    입력
    3
1 2 1
2 3 1
3 1 2
    예상 출력
    3

  2. 예제 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
    예상 출력
    35