Informatica Online Judge

  교준이의 심부름꾼, 민제의 고충 ("Minje" Ver.) [2304 / 0900]

Time Limit(Test case) : 2222 (ms)
Number of users who solved : 5   Total Tried : 6


The Champion of this Problem (C++) : gs17018 - ms / 1420byte
My Best Submission (C++) : N/A

[35th 이민제]

Background

민제는 지하철 하나 없는 대한민국의 유일한 도시 청주에서 살고 있다.

청주는 1부터 N까지 번호가 붙은 N개의 주택이 N-1개의 골목길로 연결되어 있는 작은 도시이다. 다행스럽게도 이 골목길을 통해 임의의 두 주택 사이를 오갈 수 있어서, 청주는 연결된 도시의 형태를 간신히 유지하고 있다. 한편 모든 골목길에는 구멍가게가 하나씩 있는데, 이 구멍가게에서는 각각 한 종류의 빵을 판매한다. 서로 다른 두 구멍가게가 같은 종류의 빵을 판매할 수 있다.

교준이는 매일 민제에게 빵 심부름을 시킨다. A번 주택에 있는 교준이가 B(>A)번 주택에 있는 민제에게 빵을 사 오라고 시키면, 민제는 A번 주택까지 최단 경로로 이동하면서, 지나가는 골목길에 위치하는 구멍가게에 들러 빵을 사 간다. 하지만 교준이는 같은 빵을 여러 번 먹는 것을 싫어하기에, 민제는 같은 종류의 빵을 최대 한 개만 산다. 민제는 이 조건들을 만족하면서 최대한 많은 빵을 살 것이다. (즉 민제가 사는 빵의 개수는, 민제가 지나가는 구멍가게들에서 판매하는 빵의 종류의 수와 같다.)

오늘도 역시 빵 심부름을 하던 민제는 문득 이런 궁금증이 생겼다.

"가능한 모든 (A, B) 쌍에 대해, 내가 사 가는 빵의 수를 모두 합하면 얼마일까?"

민제는 이 궁금증을 해결하고 싶었지만, "1+9+10=19"라고 말할 정도로 덧셈을 못했기에 이 문제를 풀 수 없었다. 여러분이 민제를 대신해 답을 구해주자.

Input

첫째 줄에 주택의 수 N이 주어진다.
둘째 줄부터 N-1개 줄에 걸쳐 골목길과 구멍가게의 정보가 주어진다. i+1번째 줄에는 세 개의 정수 A_i B_i C_i가 주어지는데, 이는 i번째 골목길이 A_i번 주택과 B_i번 주택을 연결하며, 이 골목길에 있는 구멍가게가 파는 빵이 C_i임을 의미한다.


*모든 입력은 아래를 만족한다.

1 <= N <= 10^5
1 <= A_i, B_i <= N
1 <= C_i <= 10^9

Output

민제가 사 가는 빵의 총 수를 정수 하나로 출력한다.

IO Example

입력 예제

4
1 2 1
1 3 1
1 4 2


출력 예제

8


(2~3)을 잇는 경로에는 서로 다른 수가 1개 있고, (2~4)를 잇는 경로에는 서로 다른 수가 2개 있다. 마찬가지로 총 6가지 가능한 경로에 대해 계산하면, 답은 1 + 1 + 1 + 1 + 2 + 2 = 8이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]