H. Пироголяндия

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 64 мегабайта

Как известно, Пироголяндия — это страна, где жители обожают пироги. В этой стране построено n пекарен, каждая из которых имеет уникальный номер от 1 до n. Каждая пекарня имеет склад, на котором хранится определенное количество пирогов, а именно, пекарня с номером i хранит a[i] пирогов.

Между некоторыми пекарнями проложены дороги, по которым можно перевозить пироги. Всего проложено n - 1 дорог, каждая из которых соединяет пекарни u[i] и v[i], позволяя перевозить любое количество пирогов между их складами в обоих направлениях.

Путем между пекарнями u и v называется последовательность уникальных номеров пекарен p[1], p[2], ..., p[k], такая, что между каждой парой p[i] и p[i+1] существует дорога, а также p[1] = u и p[k] = v. Известно, что между каждой парой пекарен существует ровно один путь, который не посещает ни одну пекарню дважды.

Иногда в Пироголяндии случаются землетрясения, из-за которых некоторые дороги могут быть перекрыты, и по ним нельзя перевозить пироги. Также дороги могут быть отремонтированы и снова открыты для перевозок. Таким образом, каждая дорога может быть либо неперекрытой, либо перекрытой.

Компонентой пекарни u называется множество всех пекарен, до которых можно добраться из пекарни u без пересечения перекрытых дорог. Сама пекарня u также входит в свою компоненту.

Одним из самых известных жителей Пироголяндии является Казак Ус, который прославился тем, что съел больше всех пирогов на ежегодном празднике пироголюбов.

В Пироголяндии происходят различные события, связанные с пекарнями, дорогами и Казаком Усом. Вам необходимо обработать m событий, представленных в виде запросов различных типов, и ответить на некоторые из них.

Существует 7 типов запросов:

Изменить состояние дороги с номером p на противоположное. Если дорога была перекрыта, она становится неперекрытой, и наоборот.
Завезти w пирогов на склад каждой пекарни, принадлежащей компоненте пекарни с номером p. То есть, если пекарня u принадлежит компоненте p, увеличить a[u] на w.
Все пекарни из компоненты пекарни p перевозят все свои пироги на склад пекарни p. После этого на складе пекарни p будут храниться все пироги из всех пекарен компоненты, а остальные склады будут пусты.
Казак Ус хочет узнать, сколько пирогов хранится на складе пекарни p, то есть значение a[p].
Казак Ус хочет узнать общее количество пирогов на складах пекарен из компоненты пекарни p.
Казак Ус съедает все пироги со склада каждой пекарни из компоненты пекарни p. После этого для каждой пекарни u из компоненты p значение a[u] становится 0.
Казак Ус хочет узнать минимальное количество дорог, которые нужно отремонтировать, чтобы он мог съесть все пироги на складах пекарен Пироголяндии, начиная путь из любой пекарни и перемещаясь только по неперекрытым дорогам.

Обратите внимание, что запросы типов 4, 5 и 7 не изменяют состояние пекарен и дорог, они только требуют ответа.

Протокол взаимодействия

Вам нужно реализовать восемь функций:

void init(integer n, array of integers u, array of integers v, array of integers b, array of integers a, integer g)

n — количество пекарен в Пироголяндии;
u[i] и v[i] (|u| = |v| = n - 1) — номера пекарен, между которыми проложена i-я дорога;
b[i] (|b| = n - 1) равно 1, если i-я дорога перекрыта, и 0 иначе;
a[i] (|a| = n) — количество пирогов в i-й пекарне;
g — номер блока;
эта функция вызывается первой и только один раз. Она сообщает количество пекарен, пары пекарен, между которыми есть дороги, состояние каждой дороги, начальное количество пирогов на складе каждой пекарни и номер блока. Только после вызова этой функции будут вызываться остальные семь.

void query_1(integer p)

p — номер дороги, состояние которой нужно изменить;
эта функция вызывается для обработки запроса первого типа.

void query_2(integer p, integer w)

p — номер пекарни;
w — количество пирогов, которые завезли в каждую пекарню компоненты пекарни p;
эта функция вызывается для обработки запроса второго типа.

void query_3(integer p)

p — номер пекарни;
эта функция вызывается для обработки запроса третьего типа.

integer query_4(integer p)

p — номер пекарни;
эта функция вызывается для обработки запроса четвертого типа;
функция должна вернуть целое число — ответ на запрос.

integer query_5(integer p)

p — номер пекарни;
эта функция вызывается для обработки запроса пятого типа;
функция должна вернуть целое число — ответ на запрос.

void query_6(integer p)

p — номер пекарни;
эта функция вызывается для обработки запроса шестого типа.

integer query_7()

эта функция вызывается для обработки запроса седьмого типа;
функция должна вернуть целое число — ответ на запрос.

Формат входных данных

Первая строка содержит три целых числа n, m и g (1 ⩽ n; m ⩽ 250 000, 0 ⩽ g ⩽ 11) — количество пекарен в Пироголяндии, количество событий и номер блока соответственно.i-я из следующих n − 1 строк содержит по два целых числа u[i] и v[i] (1 ⩽ u[i]; v[i] ⩽ n) — пара пекарен, между которыми проложена дорога с номером i. Гарантируется, что между каждой парой пекарен есть ровно один путь.

Следующая строка содержит строку из n − 1 символов 0 или 1. i-й из этих символов равен 1, если дорога с номером i перекрыта, и 0, если она не перекрыта.

Следующая строка содержит последовательность из n целых чисел a1, a2, ..., an (0 ⩽ a[i] ⩽ 10^5) — количество пирогов на складе каждой пекарни.

Каждая из следующих m строк содержит описание соответствующего запроса. Первое число в строке задает тип запроса. В случае, если запрос 2-го типа, строка содержит еще два параметра p (1 ⩽ p ⩽ n) и w (0 ⩽ w ⩽ 10^5). Если тип запроса равен 1, то строка содержит один дополнительный параметр p (1 ⩽ p ⩽ n − 1). Если тип запроса равен от 3 до 6, то строка содержит только один дополнительный параметр p (1 ⩽ p ⩽ n). В другом случае, если запрос 7-го типа, строка не содержит дополнительных параметров.

Формат выходных данных

На каждый запрос типа 4, 5 и 7 выведите ответ в отдельной строке.

Примечание

На рисунках пекарни изображены в виде круга, внутри которого заданы два целых числа — номер пекарни и количество пирогов на складе этой пекарни. Неперекрытые дороги между пекарнями изображены сплошной линией, а перекрытые пунктирной.

На рисунке 0 изображена Пироголяндия до всех изменений. Дорога с номером 2 между пекарнями с номерами 1 и 3 перекрыта. В компоненте пекарни с номером 1, так же как для пекарни с номером 2, находятся пекарни с номерами 1 и 2. В компоненте пекарен с номерами 3, 4 и 5 находятся пекарни с номерами 3, 4 и 5, следовательно, количество пирогов в пекарнях из компоненты пекарни 3 равно 6 + 1 + 3 = 10.

После второго запроса (Рис. 1) пекарни с номерами 3 и 5 перевозят свои пироги на склад пекарни с номером 4.

После третьего запроса (Рис. 2) на склад пекарен с номерами 3, 4 и 5 завезли по 4 пирога, следовательно, количество пирогов на складе пекарни с номером 3 теперь равно 4. На складе каждой пекарни, кроме пекарни с номером 2, есть хотя бы 1 пирог. Если Казак Ус начнет свой путь из пекарни с номером 1 или 2, то ему придется отремонтировать дорогу с номером 2, чтобы он мог добраться до пекарни с номером 3. Если он начнет свой путь из пекарни с номером 3 или 4, или 5, то ему придется отремонтировать ту же самую дорогу с номером 2, чтобы добраться до пекарни с номером 1. Поэтому ответ на запрос с номером 5 равен 1.

После шестого запроса (Рис. 3) Казак Ус съедает все пироги со склада пекарен с номерами 3, 4 и 5.

После седьмого запроса (Рис. 4) служба ремонта дорог отремонтирует дорогу с номером 2, поэтому теперь она становится неперекрытой. Теперь в компоненте пекарни с номером 1, так же как и для всех других пекарен, находятся все пекарни Пироголяндии. Поэтому ответ на восьмой запрос равен 0 + 1 + 0 + 0 + 0 = 1.

После девятого запроса (Рис. 5) на склад каждой пекарни завезли по 1 пирогу.

После десятого запроса (Рис. 6) из-за землетрясения разрушается дорога с номером 3, поэтому она становится перекрытой. Теперь в компоненте пекарни с номером 1 находятся все пекарни, кроме пекарни с номером 4, а в компоненте пекарни с номером 4 находится только она сама. Поэтому ответ на последний запрос равен 2 + 1 + 1 + 1 = 5.

Оценивание

(2 балла) n ⩽ 3 000; m ⩽ 3 000; нет запросов типа 1 и 7; все дороги сначала перекрыты;
(3 балла) n ⩽ 3 000; m ⩽ 3 000; нет запросов типа 1 и 7; все дороги сначала неперекрыты;
(5 баллов) n ⩽ 3 000; m ⩽ 3 000; нет запросов типа 1 и 7;
(6 баллов) n ⩽ 3 000; m ⩽ 3 000; нет запросов типа 7;
(8 баллов) n ⩽ 3 000; m ⩽ 3 000;
(10 баллов) нет запросов типа 1 и 7;
(16 баллов) нет запросов типа 7; в запросах типа 1 дороги всегда меняются только с перекрытых на неперекрытые;
(15 баллов) нет запросов типа 1;
(9 баллов) нет запросов типа 7;
(17 баллов) каждая пекарня соединена дорогой не более чем с двумя другими пекарнями;
(9 баллов) без дополнительных ограничений;