가라오케 모임

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

요약

가중치가 있는 트리에서 일부 정점이 집으로 표시되어 있습니다. 각 정점마다 가장 가까운 집까지의 거리와 가장 먼 집까지의 거리의 비율을 계산하고, 그 최댓값을 기약분수로 출력합니다.

난이도: 어려움10점 중 9점
유형: 트리, DFS, 분할 정복, 그리디
정답자: 아직 제출이 없습니다

문제

남태평양 프로그래밍 대회의 심사위원들이 다음 비밀 가라오케 모임을 계획하며 장소를 찾고 있다. 지난번에는 Timothy에게 장소를 고르게 했는데, 그는 당연히도 자기 집에서 아주 가까운 곳을 골랐고 다른 사람들과는 멀리 떨어진 곳이었다! 이번에는 공평한 모임 장소를 고르려 한다.

심사위원들은 모두 같은 도시에 살고 있다. 도시는 모임을 열 수 있는 여러 장소와 두 장소를 잇는 도로로 이루어져 있다. 도시는 임의의 두 장소 사이에 정확히 하나의 경로가 있도록 건설되었다. 각 도로에는 길이가 있고 양방향으로 다닐 수 있다. 각 심사위원의 집까지의 거리가 비슷하면 모임 장소가 공평하다고 본다. 각 장소의 공평도 점수는 A/B로, A는 그 장소에서 심사위원의 집까지의 최소 거리이고 B는 최대 거리이다. 모든 정점 중 최대 공평도 점수는 얼마인가?

입력

첫째 줄에는 도시의 장소 수 n (2 ≤ n ≤ 200 000)과 심사위원 수 k (2 ≤ k ≤ n)가 주어진다.

다음 k개 줄은 심사위원 집의 위치를 나타낸다. 각 줄에는 정수 ℓ (1 ≤ ℓ ≤ n)이 하나씩 주어지며, 이는 해당 심사위원 집의 위치이다. 두 심사위원이 같은 장소에 사는 경우는 없다.

다음 n − 1개 줄은 도시의 도로를 나타낸다. 각 줄에는 정수 u (1 ≤ u ≤ n), v (1 ≤ v ≤ n), w (1 ≤ w ≤ 10^9)가 주어지며, 이는 장소 u와 v를 잇는 길이 w의 도로이다.

출력

최대 공평도 점수를 기약분수로 출력한다.

예제4

예제 1
입력
```
3 2
2
3
1 2 1
1 3 1
```
예상 출력
```
1/1
```
예제 2
입력
```
2 2
1
2
1 2 10
```
예상 출력
```
0/1
```
예제 3
입력
```
5 3
5
2
4
3 1 1
1 4 1
1 2 1
3 5 1
```
예상 출력
```
1/2
```

예제 4

입력

예상 출력

5/16