문제
마을 N개가 N-1개의 길로 이어져 있다.
즉, 마을들은 트리 형태로 이루어져 있다.
준혁이는 1번 마을에서 시작해서 2번 마을, 3번 마을, ... , N번 마을을 순서대로 방문할 것이다.
각 길을 지나기 위해서는 통행권이 필요한데, 통행권에는 해당 길을 한 번 지나갈 수 있는 1회 통행권과, 해당 길을 몇 번이든 지나갈 수 있는 다회 통행권이 존재한다.
i번째 길의 1회 통행권의 가격은 Pi이고, 다회 통행권의 가격은 Qi이다.
준혁이가 마을들을 순서대로 방문하기 위해 통행권을 구입하는데 필요한 최소 금액을 구하여라.
입력
1번 줄 : N
2번 ~ N번 줄 : Ai Bi Pi Qi
- 2 ≤ N ≤ 200 000
- Ai, Bi는 i번 길이 잇는 마을의 번호
- Pi, Qi는 i번 길의 1회 통행권과 다회 통행권의 가격
- 1 ≤ Ai, Bi ≤ N
- 1 ≤ Pi ≤ Qi ≤ 100 000
출력
첫 번째 줄에 준혁이가 통행권을 구입하는데 필요한 최소 금액을 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 점 | 2 ≤ N ≤ 2000 |
| #2 | 점 | 모든 마을은 최대 두 개의 마을과 이어져 있다. |
| #3 | 점 | 문제의 조건 외에 주어진 제한이 없다. |
예제1
입력
4
1235
1324
2413
출력
10
예제2
입력
5
1223
1323
1423
1523
출력
11
힌트
출처
COCI 2020 Contest #5