Запити на дереві#236

Запити на дереві

1 секунда

256 мегабайтів

Складна

Дано зв'язний граф з $n$ вершинами та $n - 1$ n-1 ребром, тобто дерево. Вершина $1$ є коренем дерева. На вершині $v$ записано ціле число $a_{v}$ a_v. Вартість дерева визначається як XOR сума всіх його значень. Дано $q$ запитів, кожен з яких містить два цілі числа $v$ та $x$ . Кожен запит змінює всі значення $a_{u}$ a_u на $a_{u} \oplus x$ a_u \oplus x, де $u$ належить піддереву вершини $v$ , а $\oplus$ позначає операцію "виключне або". Як ми всі знаємо, ця задача є дуже простою для наших учасників, але якби все було так просто, ця задача не з'явилася б на цій олімпіаді. Ви знаєте, що деякі запити були змінені злим Антоном. Тому вам потрібно знайти суму вартостей за модулем $998244353$ всіх $2^{q}$ 2^q дерев, які можна отримати, застосовуючи деякі (можливо, ніякі) запити до дерева.

Вхідні дані

Перший рядок містить два цілих числа $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5) та $q$ ( $1 \leq q \leq 2 \cdot 1 0^{5}$ 1 \le q \le 2 \cdot 10^5) — кількість вершин у дереві та кількість запитів відповідно.

Другий рядок містить $n$ цілих чисел $a_{i}$ a_i ( $0 \leq a_{i} < 2^{60}$ 0 \le a_i < 2^{60}) — значення, записані на вершинах дерева.

Наступні $n - 1$ n-1 рядки містять два цілих числа $u$ та $v$ кожен — ребра заданого дерева.

Наступні $q$ рядків містять два цілих числа $v$ ( $1 \leq v \leq n$ 1 \le v \le n) та $x$ ( $0 \leq x < 2^{60}$ 0 \le x < 2^{60}) кожен — опис запитів.

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Приклади

Приклад 1

Оцінювання

( $7$ балів): $q \leq 2$ q \le 2;
( $12$ балів): $q \leq 10$ q \le 10;
( $16$ балів): $q \leq 20$ q \le 20;
( $18$ балів): $a_{i}, x < 2$ a_i, x < 2;
( $13$ балів): $a_{i}, x < 1024$ a_i, x < 1024;
( $15$ балів): $a_{i}, x < 2^{18}$ a_i, x < 2^{18};
( $19$ балів): без додаткових обмежень.