Putovanje

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

요약

트리에서 1번부터 N번 마을까지 순서대로 방문할 때, 각 간선을 지날 때마다 C1을 내거나 한 번 C2로 무제한 이용권을 사서 총비용을 최소화한다.

난이도: 보통10점 중 7점
유형: 트리, 그리디, DFS, 구현
정답자: 아직 제출이 없습니다

문제

파비얀은 술과 여행을 좋아한다. 그는 1번부터 N번까지 번호가 붙은 나라의 N개 도시에서 커피를 마시고 싶어 한다. 도시들은 (N − 1)개의 양방향 도로로 연결되어 있으며, 어떤 도시에서든 도로를 따라가면 다른 모든 도시에 도달할 수 있다. 파비얀은 도시 1번부터 N번까지 순서대로 모든 도시에서 커피를 마시기로 했다. 따라서 도시 1번에서 출발해 첫 커피를 마시고, 다음 커피를 위해 도시 2번으로 이동한다. 이동 중에 여러 도시를 지날 수 있지만 그 도시들에서는 커피를 마시지 않는다. 도시 2번에서 커피를 마신 뒤에는 도시 3번으로 이동하고, 마지막으로 도시 N번에 도착해 마지막 커피를 마실 때까지 이런 식으로 계속한다.

어떤 도로를 지나려면 유효한 티켓이 있어야 한다. i번째 도로는 Ci1유로짜리 편도 티켓이나 Ci2유로짜리 다회용 티켓이 있으면 지날 수 있다. 각 도로에 대해 파비얀은 그 도로를 지날 때마다 편도 티켓을 살지, 아니면 다회용 티켓을 한 번 살지 결정할 수 있다.

파비얀이 여행을 성공적으로 마치기 위해 티켓에 지불해야 하는 최소 유로 금액을 구하는 프로그램을 작성하시오.

입력

첫 줄에는 정수 N (2 ≤ N ≤ 200 000)이 주어진다.

다음 (N − 1)개 줄의 i번째 줄에는 네 정수 Ai, Bi, Ci1, Ci2 (1 ≤ Ai, Bi ≤ N, 1 ≤ Ci1 ≤ Ci2 ≤ 100 000)가 주어지며, 이는 도시 Ai와 Bi가 티켓 가격 Ci1, Ci2인 도로로 연결되어 있음을 나타낸다.

출력

한 줄에 여행의 최소 비용을 출력한다.

예제3

예제 1
입력
```
4
1 2 3 5
1 3 2 4
2 4 1 3
```
예상 출력
```
10
```
예제 2
입력
```
4
1 4 5 5
3 4 4 7
2 4 2 6
```
예상 출력
```
16
```
예제 3
입력
```
5
1 2 2 3
1 3 2 3
1 4 2 3
1 5 2 3
```
예상 출력
```
11
```