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

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 64 мегабайти

Як вiдомо, Пироголяндiя—країна, жителi якої дуже полюбляють пироги. Саме тому в нiй побудовано n пекарень, кожна з яких має унiкальний цiлий номер вiд 1 до n. У кожної пекарнi є свiй склад, що зберiгає певну кiлькiсть пирогiв, зокрема пекарня з номером i зберiгає a[i] пирогiв на своєму складi.

Також мiж деякими пекарнями було прокладено дороги, по яких можна перевозити пироги вiд однiєї пекарнi до iншої. Усього було прокладено n - 1 дорiг, кожна з яких має свiй унiкальний цiлий номер вiд 1 до n - 1. i - а дорога була прокладена мiж пекарнями u[i] та v[i], тобто можна перевозити будь-яку кiлькiсть пирогiв зi складу пекарнi u[i] до складу пекарнi v[i] та навпаки.

Шляхом мiж пекарнями u та v будемо називати послiдовнiсть унiкальних номерiв пекарень p[1]; p[2]; :::; p[k], таку, що iснує дорога мiж кожною парою пекарень p[i] та p[i+1], для будь-якого i вiд 1 до k - 1, а також p[1] = u та p[k] = v. Вiдомо, що мiж кожною парою пекарень iснує рiвно один шлях, що не вiдвiдує жодну пекарню двiчi.

Iнодi у Пироголяндiї трапляються землетруси, через що деякi дороги можуть ставати перекритими, а тому по них не можна перевозити пироги. Також iнодi служба ремонту дорiг може ремонтувати деякi з дорiг, пiсля чого вони стають знову доступними для перевезень. Отже, кожна дорога має мати один iз двох станiв—вона має бути або неперекритою, або перекритою.

Компонентою пекарнi u будемо називати множину всiх пекарень, до яких є шлях вiд пекарнi з номером u, що не проходить через жодну перекриту дорогу. Сама пекарня u також входить до своєї компоненти.

Одним iз найвiдомiших жителiв Пироголяндiї є Козак Вус, який отримав свою популярнiсть на тому, що з’їв бiльше всiх пирогiв на щорiчному святi пироголюбiв.

Iнодi у Пироголяндiї вiдбуваються рiзнi подiї, що пов’язанi з пекарнями, дорогами та нашим другом Козаком Вусом. Вам потрiбно вмiти оброблювати m подiй, що будуть поданi у виглядi запитiв рiзних типiв, та вмiти вiдповiдати на деякi з них.

Усього є 7 типiв запитiв:

Змiнити стан дороги з номером p на протилежний. Тобто якщо до цього запиту дорога з номером p була перекритою, то пiсля нього вона стає неперекритою, i навпаки, якщо дорога була неперекритою то вона стає перекритою.
До складу кожної пекарнi, що належить компонентi пекарнi iз номером p, завезли w пирогiв. Тобто якщо пекарня з номером u належить компонентi пекарнi p, то треба збiльшити значення a[u] на w.
Усi пекарнi з компоненти пекарнi з номером p перевозять усi свої пироги до складу пекарнi з номером p. Тобто пiсля цього запиту на складi пекарнi iз номером p будуть зберiгатись усi пироги з усiх пекарень, що знаходяться в компонентi пекарнi p, а в усiх iнших пекарнях цiєї компоненти склади будуть пустi.
Козак Вус хоче дiзнатись, скiльки пирогiв зберiгається на складi пекарнi з номером p, тобто значення a[p].
Козак Вус хоче дiзнатися сумарну кiлькiсть пирогiв, що зберiгаються на складах пекарень iз компоненти пекарнi з номером p.
Козак Вус з’їдає всi пироги зi складу кожної пекарнi з компоненти пекарнi з номером p. Тобто пiсля цього запиту для кожної пекарнi u, що належить компонентi пекарнi p, значення a[u] повинно бути рiвним 0.
Козак Вус хоче дiзнатись, яку мiнiмальну кiлькiсть дорiг треба вiдремонтувати, щоб вiн мiг з’їсти всi пироги, що зберiгаються на складах пекарень Пироголяндiї, якщо вiн може почати свiй шлях iз будь-якої пекарнi та пересуватись лише по неперекритих дорогах.

Зауважте, що запити типiв 4; 5 та 7 нiяк не впливають на пекарнi та дороги, вони лиш повиннi знаходити вiдповiдь.

####Протокол взаємодiї

Вам потрiбно реалiзувати вiсiм функцiй:

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

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

void query_1(integer p)

p — номер дороги, стан якої треба змiнити;
ця функцiя викликається, коли потрiбно задати запит першого типу.

void query_2(integer p, integer w)

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

void query_3(integer p)

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

integer query_4(integer p)

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

integer query_5(integer p)

p — номер пекарнi;
ця функцiя викликається, коли потрiбно задати запит п’ятого типу;
функцiя має повернути цiле число — вiдповiдь на запит.

void query_6(integer p)

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

integer query_7()

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

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

Наступний рядок мiстить рядок з n − 1 символiв 0 або 1. i-й з цих символiв рiвний 1, якщо дорога з номером i перекрита, та 0, якщо вона не перекрита.

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

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

Вихідні дані

На кожний запит типу 4, 5 та 7 виведiть вiдповiдь в окремому рядку.

####Оцiнювання

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

####Примiтка

На малюнках пекарнi зображенi у виглядi кола, всерединi якого задано два цiлi числа — номер пекарнi та кiлькiсть пирогiв на складi цiєї пекарнi. Неперекритi дороги мiж пекарнями зображено суцiльною лiнiєю, а перекритi пунктирною.

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

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

Пiсля третього запиту (Мал. 2) до складу пекарень з номерами 3, 4 та 5 завезли по 4 пироги, отже, кiлькiсть пирогiв на складi пекарнi з номером 3 тепер рiвна 4. На складi кожної пекарнi, окрiм пекарнi з номером 2, є хоча б 1 пирiг. Якщо Козак Вус почне свiй шлях iз пекарнi з номером 1 або 2, то йому доведеться вiдремонтувати дорогу з номером 2, щоб вiн мiг дiстатись пекарнi з номером 3. Якщо вiн почне свiй шлях з пекарнi з номером 3 або 4, або 5, то йому доведеться вiдремонтувати ту ж саму дорогу з номером 2, щоб дiстатись до пекарнi з номером 1. Тому вiдповiдь на запит з номером 5 рiвна 1.

Пiсля шостого запиту (Мал. 3) Козак Вус з’їдає всi пироги зi складу пекарень з номерами 3, 4 та 5.

Пiсля сьомого запиту (Мал. 4) служба ремонту дорiг вiдремонтує дорогу з номером 2, тому тепер вона стає неперекритою. Тепер у компонентi пекарнi з номером 1, так само як i для всiх iнших пекарень, знаходяться всi пекарнi Пироголяндiї. Тому вiдповiдь на восьмий запит рiвна 0 + 1 + 0 + 0 + 0 = 1.

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

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