Karaoke Meetup

时间限制: 1 Sec  内存限制: 128 MB

题目描述

The judges of the South Pacific Programming Contest are planning their next secret karaoke meetup and are looking for a place to hold it. Last time, they asked Timothy to pick the location, but of course, he just picked somewhere really close to his house, and far from everyone else’s! This year, you would like to pick a meeting location that is fair.
All the judges live in the same city. The city consists of various locations in which the meeting could be held and roads that connect pairs of locations.
The city is built such that for each pair of locations, there is exactly one path between them. Each road has a length and can be used to travel in either direction. You consider a meeting point fair if the distances from each of the judges’ houses are similar. For each location, its fairness score is the ratio A/B, where A is the minimum distance from the location to any judges’ house and B is the largest distance. What is the maximum fairness score for all vertices?

输入

The first line contains two integers n (2 ≤ n ≤ 200 000), which is the number of locations in the city, and k (2 ≤ k ≤ n), which is the number of judges.
The next k lines describe the location of the judges’ houses. Each of these lines contains a single integer L (1 ≤ L ≤ n), which is the location of this judge’s house. No two judges live at the same location.
The next n − 1 lines describe the roads in the city. Each of these lines contains three integers u (1 ≤ u ≤ n), v (1 ≤ v ≤ n), and w (1 ≤ w ≤ 10⁹), which denotes a road between locations u and v with a length of w.

输出

Display the maximum fairness score as a reduced fraction.

样例输入

样例1

样例2

样例3

样例4

样例输出

样例1

样例2

样例3

样例4

题解

化用树形dp求树上每个点可以到达的最远距离，p[x][0]表示以x为根向下可以到达的最远距离（f[x][0]）以及从哪个孩子转移过来，p[x][1]表示以x为根向下可以到达的“次远距离”以及从哪个孩子转移过来（并不是严格意义上的次远距离，要从和最远不同的点转移过来）；f[x][1]表示从x向上（向父亲方向）可以到达的最远距离。

最短距离也可以通过树形dp来求，对于这个题，可以添加一个超级源点，把树化为图求最短路。

代码