G. Критерий в Бурляндии
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Регионы в Бурляндии образуют граф из $$$n$$$ вершин, и $$$n-1$$$ ребра, причём между любыми двумя вершинами существует ровно один путь. Формально говоря, регионы образуют дерево.

Каждый регион имеет характеристику дружелюбия $$$a_i$$$.

Дано $$$q$$$ запросов. В каждом запросе задаётся пара друзей, находящихся в разных регионах. Им интересно узнать, сколько существует подотрезков пути между этими регионами, которые являются гостеприимными.

Известно, что в Бурляндии существует два критерия оценки взаимоотношений — XOR и сумма. Подотрезок пути, содержащий некоторые вершины, лежащие на пути от региона $$$x$$$ до региона $$$y$$$, называется гостеприимным, если он непустой и сумма значений дружелюбия на этом подотрезке не превышает их XOR.

Более формально, для каждого запроса вам даны две вершины $$$x$$$ и $$$y$$$ $$$(x \neq y)$$$. Рассмотрим кратчайший путь от вершины $$$x$$$ до вершины $$$y$$$ в дереве. Пусть вершины $$$v_1, v_2, \ldots, v_k$$$ образуют этот путь, при чем $$$v_1 = x$$$, $$$v_k = y$$$. Требуется найти количество подотрезков этого пути, для которых выполняется следующее условие: $$$$$$ a_{v_{l}} \oplus a_{v_{l+1}} \oplus \ldots \oplus a_{v_{r}} \geq (a_{v_{l}} + a_{v_{l+1}} + \ldots + a_{v_{r}}), $$$$$$ где $$$1 \leq l \leq r \leq k$$$ — границы подотрезка вершин на пути от $$$x$$$ до $$$y$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов.

Первая строка каждого набора входных данных содержит целые числа $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество вершин дерева, и $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — количество запросов.

Во второй строке задаётся массив из $$$n$$$ целых неотрицательных чисел — характеристики дружелюбия регионов ($$$0 \leq a_i \lt 2^{20}$$$).

В следующих $$$n - 1$$$ строках описаны рёбра дерева: в каждой строке даны числа $$$u, v$$$ ($$$1 \leq u, v \leq n$$$) — очередное ребро.

Затем следуют $$$q$$$ строк с описанием запросов. Каждый запрос задаётся числами $$$x, y$$$ ($$$1 \leq x, y \leq n$$$, $$$x \neq y$$$) — вершины, задающие путь, для которого нужно посчитать количество гостеприимных отрезков.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$, а также что рёбра действительно задают дерево.

Выходные данные

Для каждого запроса выведите ответ на него в отдельной строке.

Пример
Входные данные
3
4 3
0 0 4 1
1 2
1 3
1 4
1 4
2 3
2 4
4 3
0 4 1 2
1 3
1 4
2 4
1 2
2 3
2 4
4 3
3 2 4 4
1 2
2 4
3 4
1 2
1 3
2 3
Выходные данные
3
6
6
6
10
3
2
5
4
Примечание

Для наглядности разберём третий запрос из третьего примера.

Путь от вершины $$$2$$$ до вершины $$$3$$$ образуют вершины $$${2, 4, 3}$$$.

Подотрезок $$$[2; 3]$$$ не подходит, так как XOR на нём равен $$$a_4 \oplus a_3 = 4 \oplus 4 = 0$$$, а сумма равна $$$a_4 + a_3 = 4 + 4 = 8$$$.

Подотрезок $$$[1; 3]$$$ не подходит, так как XOR на нём равен $$$a_2 \oplus a_4 \oplus a_3 = 2 \oplus 4 \oplus 4 = 2$$$, а сумма равна $$$a_2 + a_4 + a_3 = 2 + 4 + 4 = 10$$$.

Можно показать, что все остальные 4 отрезка удовлетворяют условию задачи.