Tree queries#236

Tree queries (Editorial)

Спершу спростимо вплив одного запиту на вартість дерева.

Запит $(v, x)$ додає $x$ (за XOR) до всіх вершин піддерева $v$ . Вартість дерева — це XOR усіх значень, тому в неї це $x$ увійде рівно стільки разів, скільки вершин у піддереві. Але $x \oplus x = 0$ x \oplus x = 0, отже важлива лише парність розміру піддерева:

якщо $∣ subtree (v) ∣$ парний, запит взагалі не змінює вартість;
якщо непарний, вартість змінюється на $\oplus x$ .

Позначимо $A$ — XOR усіх початкових значень $a_{u}$ a_u, і назвемо запит суттєвим, якщо розмір його піддерева непарний. Тоді для будь-якої підмножини запитів $S$ вартість дорівнює

A \oplus j \in S, j суттєвий ⨁ x_{j} .

A \oplus \bigoplus_{j \in S,\ j \text{ суттєвий}} x_j.

Тепер порахуємо суму по всіх $2^{q}$ 2^q підмножинах побітово. Зафіксуємо біт $b$ і подивимось, у скількох підмножинах він дорівнює одиниці.

Якщо жоден суттєвий запит не має біта $b$ , то цей біт результату завжди дорівнює біту $b$ числа $A$ . Отже, він одиничний або в усіх $2^{q}$ 2^q підмножинах, або в жодній.
Якщо ж хоча б один суттєвий запит має біт $b$ , то рівно половина підмножин дає одиницю. Це видно з простої бієкції: зафіксуємо один такий запит і зіставимо кожній підмножині ту, що відрізняється лише його наявністю — це розбиває всі підмножини на пари з протилежними значеннями біта. Отже, рівно $2^{q - 1}$ 2^{q-1} підмножин.

Тому відповідь дорівнює

b \sum 2^{b} \cdot ⎩ ⎨ ⎧ 2^{q - 1}, 2^{q}, 0, якщо якийсь суттєвий x_{j} має біт b; інакше і біт b числа A одиничний; інакше,

\sum_{b} 2^b \cdot \begin{cases} 2^{q-1}, & \text{якщо якийсь суттєвий } x_j \text{ має біт } b;\\ 2^q, & \text{інакше і біт } b \text{ числа } A \text{ одиничний};\\ 0, & \text{інакше,} \end{cases}

усе за модулем $998244353$ .

Розміри піддерев (точніше, їхні парності) рахуються одним обходом у глибину. Значення сягають $2^{60}$ 2^{60}, тому перебирайте біти до $59$ -го включно і не забувайте, що степені двійки в сумі теж треба брати за модулем.