Codeforces Round 264 (Div. 2) |
---|
Закончено |
Caisa сейчас дома и его сын придумал для него простую задачку.
Задано корневое дерево, состоящее из n вершин, пронумерованных от 1 до n (вершина 1 — корень дерева). В каждой вершине записано некоторое значение. Требуется ответить на q запросов. Каждый запрос является одним из следующих:
Вам заданы все запросы, помогите Caisa справиться с этой задачей.
В первой строке записаны два целых числа n, q (1 ≤ n, q ≤ 105).
Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 2·106), где ai обозначает значение, записанное в вершине i изначально.
В каждой из следующих n - 1 строк записаны два целых числа xi и yi (1 ≤ xi, yi ≤ n; xi ≠ yi), обозначающие, что в дереве есть ребро между вершинами xi и yi.
В каждой из следующих q строк задан запрос в формате, описанном выше. Для каждого запроса выполняются следующие неравенства: 1 ≤ v ≤ n и 1 ≤ w ≤ 2·106. Обратите внимание: не более 50 запросов из всех меняют значение в вершине.
Для каждого запроса первого типа выведите ответ на него.
4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4
-1
1
2
-1
1
Запись gcd(x, y) обозначает наибольший общий делитель целых чисел x и y.
Название |
---|