철도 노선 덮기

시간 제한1초메모리 제한128 MB

요약

트리에서 모든 정점을 겹치지 않는 경로들로 분할해 모든 정점을 덮으면서 사용된 변의 가중치 합을 최대화하는 문제이며 트리 DP로 해결합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 트리, 그리디
정답자: 아직 제출이 없습니다

문제

어느 나라의 철도망은 여러 개의 철도 구간으로 이루어져 있습니다. 각 구간은 서로 다른 두 마을을 연결하며, 모든 구간의 길이가 주어집니다. 이 철도망에서는 임의의 두 마을 사이를 잇는 경로가 정확히 하나만 존재합니다.

철도 회사는 새 고속 열차를 운행하기 위해 열차 노선을 다시 정하려고 합니다. 하나의 노선은 두 개 이상의 마을로 이루어진 순서 있는 목록이며, 목록에서 이웃한 두 마을은 반드시 철도 구간으로 직접 연결되어 있어야 합니다. 노선의 길이는 그 노선에 포함된 철도 구간 길이의 합입니다.

열차가 매우 빠르기 때문에 서로 다른 두 노선이 같은 마을을 지나서는 안 됩니다. 모든 마을은 정확히 하나의 노선에 포함되어야 합니다.

위 조건을 만족하도록 노선들을 정할 때, 모든 노선 길이의 합이 최대가 되도록 하세요.

입력

첫째 줄에 마을의 수 N이 주어집니다. 1 <= N <= 2000입니다. 마을은 1번부터 N번까지 번호가 붙어 있습니다.

다음 N-1개 줄에는 철도 구간의 정보가 주어집니다. 각 줄에는 세 정수 A, B, C가 주어지며, 이는 A번 마을과 B번 마을을 잇는 길이 C의 구간을 뜻합니다. 1 <= C <= 1,000,000입니다.

주어지는 입력에는 항상 조건을 만족하는 노선 배치가 존재합니다.

출력

문제의 조건을 만족하는 노선 배치 중, 모든 노선 길이의 합의 최댓값을 첫째 줄에 출력합니다.

예제3

예제 1
입력
```
5
1 2 10
1 3 10
1 4 10
4 5 1
```
예상 출력
```
21
```
예제 2
입력
```
6
1 2 1
1 3 3
1 4 7
2 5 4
2 6 6
```
예상 출력
```
20
```

예제 3

입력

예상 출력