Большая Древесная База Данных создана для того, чтобы в ней можно было надежно сохранить и раскрасить любое дерево. В новой версии БДБД запланирован новый функционал, для реализации которого потребуется вновь переосмыслить теорию графов.
В БДБД хранится взвешенное дерево. В языке запросов Системы Управления Большой Древесной Базы Данных (СУБДБД) предусмотрены два вида запросов:
Необходимо запрограммировать работу СУБДБД и ответить на все запросы пользователя.
В первой строке число N (1 ≤ N ≤ 105) — количество вершин дерева.
Следующие N - 1 строк содержат описание ребер, по три числа в строке ai, bi, wi (1 ≤ ai, bi ≤ N, ai ≠ bi, 1 ≤ wi ≤ 104), где i-ое ребро имеет вес wi и соединяет вершины ai и bi.
В следующей строке число Q (1 ≤ Q ≤ 105) — число запросов. В каждой из Q следующих строк запросы одного из двух видов:
Все числа во входных данных целые.
Для каждого запроса второго типа необходимо вывести в отдельной строке цвет запрошенной вершины.
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
Название |
---|