После (наконец-то) прохождения отбора на IOI 2023, wxhtzdy был очень счастлив и решил сделать то, что делают многие люди: попытаться угадать задачи, которые будут на IOI. В процессе этого он случайно создал задачу, которая, по его мнению, была очень крутой.
Дано дерево (связный ациклический граф) с \(n\) вершинами и \(n-1\) ребром. Вершине \(i\) (\(1 \le i \le n\)) соответствует значение \(a_i\). Пусть \(g(u, v)\) - это побитовое ИЛИ значений всех вершин на кратчайшем пути от \(u\) до \(v\). Например, если мы хотим вычислить \(g(3, 4)\) на дереве из первого набора данных примера. На пути от \(3\) до \(4\) находятся вершины \(3\), \(1\), \(4\). Тогда \(g(3, 4) = a_3 \ | \ a_1 \ | \ a_4\) (здесь \(|\) обозначает побитовое ИЛИ).
Также дано \(q\) запросов, и каждый запрос выглядит следующим образом:
Вам даны \(x\) и \(y\). Рассмотрим все вершины \(z\) такие, что \(z\) находится на кратчайшем пути от \(x\) до \(y\) (включительно).
Определим красоту вершины \(z\) как сумму количества ненулевых битов в \(g(x, z)\) и количества ненулевых битов в \(g(y, z)\). Вам нужно найти максимальную красоту среди всех вершин \(z\) на кратчайшем пути от \(x\) до \(y\).
Так как его мозг очень устал после решения output only задачи на SIO (он должен был это сделать, чтобы пройти отбор на IOI), он хочет вашей помощи в этой задаче.
Выходные данные
Для каждого набора входных данных выведите \(q\) целых чисел, каждое из которых является ответом на соответствующий запрос.
Примечание
На изображении ниже показано дерево из первого набора входных данных второго примера.
Дерево из первого набора входных данных второго примера. В первом запросе \(x=7\), \(y=5\). Самый короткий путь от \(7\) до \(5\) это \(7-4-2-1-5\).
Давайте вычислим красоту вершины \(7\) на этом пути. У нас есть \(g(7,7)=a_7=10=(1010)_2\) и \(g(5,7)=a_5 \ | \ a_1 \ | \ a_2 \ | \ a_4 \ | \ a_7=10 \ | \ 4 \ | \ 7 \ | \ 4 \ | \ 10=15=(1111)_2\), поэтому ее красота равна \(2 + 4 = 6\).
Теперь давайте вычислим красоту вершины \(4\) на этом пути. У нас есть \(g(7,4)=a_7 \ | \ a_4=10 \ | \ 4=14=(1110)_2\) и \(g(5,4)=a_5 \ | \ a_1 \ | \ a_2 \ | \ a_4=10 \ | \ 4 \ | \ 7 \ | \ 4=15=(1111)_2\), поэтому ее красота равна \(3 + 4 = 7\).
Теперь давайте вычислим красоту вершины \(2\) на этом пути. У нас есть \(g(7,2)=a_7 \ | \ a_4 \ | \ a_2=10 \ | \ 4 \ | \ 7=15=(1111)_2\) и \(g(5,2)=a_5 \ | \ a_1 \ | \ a_2=10 \ | \ 4 \ | \ 7=15=(1111)_2\), поэтому ее красота равна \(4 + 4 = 8\).
Теперь давайте вычислим красоту вершины \(1\) на этом пути. У нас есть \(g(7,1)=a_7 \ | \ a_4 \ | \ a_2 \ | \ a_1=10 \ | \ 4 \ | \ 7 \ | \ 4=15=(1111)_2\) и \(g(5,1)=a_5 \ | \ a_1=10 \ | \ 4=14=(1110)_2\), поэтому ее красота равна \(4 + 3 = 7\).
Наконец, давайте вычислим красоту вершины \(5\) на этом пути. У нас есть \(g(7,5)=a_7 \ | \ a_4 \ | \ a_2 \ | \ a_1 \ | \ a_5=10 \ | \ 4 \ | \ 7 \ | \ 4 \ | \ 10=15=(1111)_2\) и \(g(5,5)=a_5=10=(1010)_2\), поэтому ее красота равна \(4 + 2 = 6\).
Максимальная красота на этом пути у вершины \(2\), и она равна \(8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1 2 3 4
1 3
1 2
1 4
3
1 1
1 3
1 4
3
7 6 3
3 1
2 1
4
1 1
1 2
1 3
2 3
1
4
1
1 1
|
2 4 3
6 6 6 6
2
|
|
2
|
3
7
4 7 7 4 10 8 10
6 1
3 1
2 1
7 4
1 5
4 2
4
7 5
2 3
4 5
2 5
6
9 5 6 2 4 6
5 1
2 1
1 6
4 3
1 3
4
6 1
1 4
4 3
3 5
7
5 1 3 7 5 1 6
2 1
5 4
2 3
3 4
7 6
6 3
2
4 2
7 7
|
8 6 7 7
6 6 4 7
6 4
|
|
3
|
1
7
6 8 7 2 5 8 7
2 1
3 2
4 3
4 6
4 5
6 7
4
1 5
6 7
4 5
1 4
|
7 7 5 7
|