Informatica Online Judge

  민제의 은신 #1 [2382 / 094E]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 12   Total Tried : 12


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

[36th 정성재(gs17105)]
Writer ID : [gs17105]

Background

감옥에서 탈출한 민제는 서현중로의 아파트 단지로 돌아갔다.
이 아파트 단지는 트리 형태를 이루고 있으며,
1동~n동의 n개 동과 n-1개의 길로 이루어져 있다.

그런데 간수 은교준이 민제를 쫓아왔다.
민제는 급한 대로 아파트 두 개 동을 정해,
그 두 동을 잇는 길을 제외한 모든 길을 폐쇄하였다.
폐쇄되지 않은 길과 이 길에 연결된 동을 모두 모은 것이 민제의 은신처이다.
그리고 폐쇄되지 않은 길의 길이의 총합을 은신처의 길이라 한다.

은교준은 민제의 은신처에 침입하여 민제를 잡으려 한다.
하지만 은교준은 지난 t년 동안의 IOI에서
각각 k_i점을 받아 은메달을 땄기 때문에,
길이가 k_i인 은신처에는 침입하지 못한다.
(k_i들은 서로 다르다는 것이 보장된다.)

민제를 위해 은교준이 침입하지 못하는 은신처의 개수를 구해주자.

Input

첫 번째 줄에는 아파트 동의 개수 n과 은교준의 IOI 참가 횟수 t가 주어진다.

두 번쨰 줄에는 은교준의 IOI 점수 k_i (1 <= i <= t)가 공백으로 구분되어 주어진다.

세 번째 줄부터 n-1줄에 걸쳐 길에 대한 정보가 주어진다.
길의 정보는 길의 양 끝 동 x, y와 길의 길이 z가 x y z 형태로 주어진다.

1 <= n <= 1,000
1 <= t <= 10
1 <= k_i <= 10,000
1 <= z_i <= 100

Output

은교준이 침입하지 못하는 은신처의 개수를 출력하여라.

IO Example

입력
6 2
1 2
1 2 1
2 3 1
3 4 1
3 5 1
3 6 1

출력
12

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