Problems
N개의 도시와, 그들을 모두 연결하고 있는 N-1개의 양방향 항로가 있다.
각 항로마다 길이가 주어지고, 각 도시는 드론 충전소를 보유하고 있다.
드론은 1km 당 1의 배터리를 소모한다.
드론이 각 도시에 도착할 때, 그 도시에 있는 충전소에서 배터리를 충전할 수 있다.
각 도시의 충전소마다 배터리를 충전해주는 정도가 다르다.
배터리가 없는 상태로, 도시 A에서 출발하여, 모든 도시를 최대 1번만 방문하여 도시 B까지 도달할 수 있는 도시 쌍 (A, B)의 개수를 구하자.
당연히, 배터리가 없는 상태로 출발하기 때문에, 출발지 A 에서 충전을 하고 출발할 것이다.
Input
첫 줄에 도시의 수 N(1 ≤ N ≤ 105)을 입력 받는다.
두 번째 줄에 N개의 정수 Ai(1 ≤ Ai ≤ 109)를 입력 받으며, Ai는 i번째 도시에 있는 충전소의 충전량을 나타낸다.
다음 N-1개의 줄에는 각각 세 개의 정수 U, V (1 ≤ U, V ≤ N, U ≠ V), W(1 ≤ W ≤ 109)를 입력 받으며,
이는 U번 도시와 V번 도시 사이에 길이 W의 양방향 항로가 존재함을 나타낸다.
Output
조건을 만족하는 도시 쌍 (A, B) 의 개수를 출력하자.
Example #1
2
3 1
1 2 2
1
도시 1 → 도시 2 만 가능하다.
도시 2 → 도시 1 은, 출발할 당시 1의 배터리만 충전되기에 불가능하다.
Example #2
5
3 1 2 4 5
1 2 3
3 2 2
4 2 6
5 4 3
5
(1, 2), (3, 2), (4, 5), (5, 1), (5, 4)
Example #3
8
5 2 4 7 8 3 3 6
6 5 5
1 4 5
3 1 2
8 6 5
1 2 3
4 5 3
4 7 5
29
You must sign in to write code.