An Extraordinarily Coordinated Christmas

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

It's Christmas! Santa has joined the World Health Organization. Being in the middle of a pandemic, Santa will need to use his delivery skills to deliver vaccines instead of presents.

Being the genius he is, he developed a system called T.M.A.S (TMAS: Modern Accelerated Sender) that can deliver vaccines through a distributed network of cities at great speeds!

The T.M.A.S network of the world is represented as a tree with N cities and N-1 bi-directional routes that Santa can take. In fact, each connection between two cities u_i and v_i will be w_i kilometers in length. To test the effectiveness of this system, Santa decides to send vaccines as far as possible from a given node.

He will give you Q cities. For each city, find the furthest distance away from the city that he can send the vaccine.

Input Specification

The first line contains two integers N (1 \le N \le 10^5) and Q (1 \le Q \le 10^5), the number of cities and the number of queries respectively.

Each of the next N-1 lines contains three integers u, v (1 \le u,v \le N) and w (1 \le w \le 10^3) indicating a bi-directional connection between u and v with distance w.

Each of the next Q lines will contain a city x (1 \le x \le N) for which you must print the furthest distance away from this city.

For 20\% of the test cases N (1 \le N \le 10^3) and Q (1 \le Q \le 10^3).

Output Specification

For each x in the given query, print the furthest distance that Santa is able to achieve.

Sample Input

6 3
2 1 4
6 3 1
4 3 5
3 2 2
5 3 2

Sample Output



For city 3 the furthest city away is 1 with a distance of 2+4 = 6.

For city 2 the furthest city away is 4 with a distance of 2+5 = 7.

For city 1 the furthest city away is 4 with a distance of 4+2+5 = 11.


There are no comments at the moment.