402826: GYM100889 J Jittery Roads

You have just visited a country which consists of N cities, with exactly one path between every pair of cities(i.e. the country forms a weighted undirected tree with N vertices).

A non-empty subset of all the cities form a set of "special" cities. For every "special" city, you need to find what is the farthest distance from that city to any other "special" city. But since the country is still developing, the roads between two cities can change and the set of "special" cities also keep changing.

First line contains N(1 ≤ N ≤ 10⁵), followed by N - 1 lines each containing three values u v w, which means that there is a road between cities u and v with distance w(1 ≤ u, v ≤ N and 1 ≤ w ≤ 10⁹).

The next line contains Q(1 ≤ Q ≤ 10⁵), the number of queries. The next Q queries contain an integer 1 or 2 in one line, indicating the type of query.

For each type, the next line in the input is of the format:

• u v w : Update the weight of edge between u and v to w(1 ≤ u, v ≤ N and 1 ≤ w ≤ 10⁹).
• An integer K(1 ≤ K ≤ N) followed by the K integers denoting the set of "special" cities for current query.

Note that sum of K over all queries  ≤ 5 * 10⁵.

For each query of type 2, print a single line with K values which is the answer for each of those "special" cities.

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

5 3 5 
8 5 8 

For first query:

For city 5, city 4 is farthest "special city" at distance 5 and vice-versa. For city 2, city 5 is farthest "special city" at distance 3.