| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 9 초 | 1024 MB | 5 | 3 | 3 | 60.000% |
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 \le N \le 10^5$) --- the number of tree vertices. The following N-1 lines contain the description of branches, three numbers in each line $a_i$, $b_i$, $w_i$ ($1 \le a_i, b_i \le N$, $a_i \ne b_i$, $1 \le w_i \le 10^4$), where $i$-th branch with weight $w_i$ connects vertices $a_i$ and $b_i$. The next line contains integer Q ($1 \le Q \le 10^5$) --- 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