402826: GYM100889 J Jittery Roads

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Jittery Roadstime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

First line contains N(1 ≤ N ≤ 105), 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 ≤ 109).

The next line contains Q(1 ≤ Q ≤ 105), 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 ≤ 109).
  • 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 * 105.

Output

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

ExampleInput
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
Output
5 3 5 
8 5 8
Note

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.

加入题单

上一题 下一题 算法标签: