2015 ICL, Finals, Div. 1 |
---|
Finished |
The Large Wood Database is created to securely store and paint any existing tree. Update for LWDB provides new functionality, so it is time to think over the graph theory. A weighed tree is stored in the LWDB. In the query language for LWDB Management System (LWDB MS) two types of queries are available:
It is required to prototype LWDB MS and respond to all user’s queries.
The first line contains an integer N (1 ≤ N ≤ 105) — the number of tree vertices. The following N-1 lines contain the description of branches, three numbers in each line ai, bi, wi (1 ≤ ai, bi ≤ N, ai ≠ bi, 1 ≤ wi ≤ 104), where i-th branch with weight wi connects vertices ai and bi. The next line contains integer Q (1 ≤ Q ≤ 105) — number of queries. In each of Q following lines there are two types of queries:
Input numbers are integers.
For each second type query output the color of requested vertice in a separate line.
5
1 2 30
1 3 50
3 4 70
3 5 60
8
1 3 72 6
2 5
1 4 60 5
2 3
2 2
1 2 144 7
2 4
2 5
6
6
0
5
7
Name |
---|