Дан связный неориентированный граф без циклов (то есть дерево) на \(n\) вершинах, при этом на каждом ребре написано какое-то целое неотрицательное число.
Рассмотрим все пары вершин \((v, u)\) (то есть всего \(n^2\) таких пар) и для каждой пары посчитаем побитовое исключащее ИЛИ (xor) всех чисел на рёбрах на простом пути между \(v\) и \(u\). Если путь состоял только из одной вершины, то xor всех чисел на рёбрах этого пути считается равным \(0\).
Предположим, мы отсортировали полученные \(n^2\) значений по неубыванию. Требуется вывести \(k\)-е из них.
Операция xor определяется следующим образом:
Пусть даны два целых неотрицательных числа \(x\) и \(y\), рассмотрим их двоичные записи (возможно с ведущими нулями): \(x_k \dots x_2 x_1 x_0\) и \(y_k \dots y_2 y_1 y_0\) (где \(k\) любое число, что все биты \(x\) и \(y\) могут быть представлены). Здесь \(x_i\) это \(i\)-й бит числа \(x\), а \(y_i\) это \(i\)-й бит числа \(y\).
Пусть \(r = x \oplus y\) — результат операции xor над числами \(x\) и \(y\). Тогда двоичной записью \(r\) будет \(r_k \dots r_2 r_1 r_0\), где:
\(\) r_i = \left\{ \begin{aligned} 1, ~ \text{если} ~ x_i \ne y_i \\ 0, ~ \text{если} ~ x_i = y_i \end{aligned} \right. \(\)