\begin{tutorial}{Простая задача}

\begin{center}
\textit{Автор задачи и разработчик: Алексей Васильев}
\end{center}

Изначально посчитаем вспомогательный массив $closest_{v, b}$~--- расстояние до ближайшей вершины к $v$, число в который содержит единичный бит $b$ ($0 \leq b < k$). Решим это независимо по битам. Когда мы хотим посчитать $closest$ для какого-то конкретного бита, то запустим multisource bfs из всех вершин, которые содержат этот единичный бит. Либо можно сделать это с помощью динамики по поддеревьям. Асимптотика этой части $O(n k)$.

Пусть мы знаем ответное множество $A$, зафиксируем в нем вершины на максимальном расстоянии. Пусть это вершины $a$ и $b$. Назовем путь между этими вершинами диаметром, а длиной этого диаметра~--- количество ребер в нем (обозначим длину как $d$). 

Разберем два случая:

\begin{enumerate}

\item Пусть длина диаметра четная. Пусть вершина $m$~--- середина диаметра. Тогда все вершины из $A$ находятся на расстоянии не больше $\frac{d}{2}$ от $m$ (если это не так, то можно показать, что мы взяли неправильный диаметр). Это значит, что от того, что мы возьмем в ответное множество все вершины на расстоянии не больше $\frac{d}{2}$ от $m$, то нам хуже не станет (то есть множество не уменьшится и стоимость этого множества останется прежней).

Обработаем этот случай следующим образом. Зафиксируем вершину $m$. Теперь мы хотим найти минимальное $x$, что если набрать в ответное множество все вершины на расстоянии не более $x$ от $m$, то у них будет нужное нам значение ИЛИ. Утверждается, что $x$~--- это максимальное значение $closest_{m, b}$ по всем битам $b$. Таким образом мы находим это $x$ и релаксируем ответ через $2x$ (потому что $x$~--- это $\frac{d}{2}$).

\item Пусть длина диаметра нечетная. Тогда у него посередине не вершина, а ребро. Пусть вершины ребра посередине~--- это $m_1$ и $m_2$. Тогда аналогично прошлому пункту, мы говорим, что все вершины множества $A$ находятся на расстоянии не более $\frac{d - 1}{2}$ от вершины $m_1$ или от вершины $m_2$. И от того, что мы возьмем в ответное множество все вершины на расстоянии не более $\frac{d - 1}{2}$ от $m_1$ или $m_2$, нам хуже не станет.

Поэтому аналогично прошлому пункту~--- перебираем ребро $m_1, m_2$. Дальше хотим найти минимальное $x$, такое что, если набрать в ответное множество все вершины на расстоянии не более $x$ от $m_1$ или $m_2$, то у них будет нужное нам значение ИЛИ. Утверджается, что $x$~--- это максимальное значение $min(closest_{m_1, b}, closest_{m_2, b})$. Находим это $x$ и релаксируем ответ через $2x + 1$ (потому что $x$~--- это $\frac{d - 1}{2}$).

Можно еще не думать отдельно про второй случай следующим образом: добавим посередине каждого ребра фиктивную вершину с значением 0 и будем решать на таком новом дереве. После такой модификации дерева центром ответного диаметра всегда будет вершина, поэтому можно думать только про первый случай.

\end{enumerate}

Асимптотика второй части $O(n k)$, потому что мы перебрали $O(n)$ кандидатов на центр диаметра и для каждого вычислили $x$ за $O(k)$.

\end{tutorial}
