Codeforces Round 225 (Div. 1) |
---|
Закончено |
Яхуб очень любит деревья. Недавно он обнаружил интересное дерево под названием «дерево подвижных сумм». Дерево состоит из n вершин, пронумерованных от 1 до n, каждая вершина i содержит начальное значение ai. Корень дерева — вершина 1.
Это дерево имеет особое свойство: когда значение val добавляется к значению вершины i, значение -val добавляется ко всем значениям детей вершины i. Обратите внимание, что когда вы добавляете значение -val ребенку вершины i, вы также добавляете -(-val) ко всем детям этого ребенка вершины i и так далее. Для того, чтобы лучше понять описанное свойство, обратите внимание на пояснение к первому тесту.
Дерево поддерживает два типа запросов:
Чтобы помочь Яхубу лучше понять дерево, надо ответить на m запросов описанных типов.
В первой строке содержатся два целых числа n и m (1 ≤ n, m ≤ 200000). Во второй строке содержится n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 1000). В каждой из следующих n–1 строк содержится по два целых числа, ui и vi (1 ≤ ui, vi ≤ n), означающих, что существует ребро между вершинами ui и vi.
Каждая из следующих m строк содержит запрос в описанном выше формате. Гарантируется, что для всех запросов выполняется: 1 ≤ x ≤ n, 1 ≤ val ≤ 1000.
Для каждого запроса второго типа (вывод текущего значения вершины) надо вывести ответ на запрос на отдельной строке. Ответы на запросы выводите в порядке следования запросов во входных данных.
5 5
1 2 1 1 2
1 2
1 3
2 4
2 5
1 2 3
1 1 2
2 1
2 2
2 4
3
3
0
Изначально значения в вершинах равны [1, 2, 1, 1, 2].
Затем значение 3 добавляется к вершине 2. Вершина 2 передает значение -3 своим сыновьям, и далее значение -3 добавляется к вершинам 4 и 5. Дальше значение никуда не передается. После этого запроса значения в вершинах равны [1, 5, 1, - 2, - 1].
Затем значение 2 добавляется к вершине 1. Вершина 1 передает значение -2 своим сыновьям: вершине 2 и вершине 3. Из вершины 2 значение 2 передается вершинам 4 и 5. Вершина 3 не имеет сыновей, следовательно из нее значение не передается. После этого запроса значения в вершинах становятся равны [3, 3, - 1, 0, 1].
С основными определениями, связанными с корневыми деревьями, можно ознакомиться по ссылке: http://ru.wikipedia.org/wiki/Дерево_(теория_графов)
Название |
---|