\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}
\begin{document}
\renewcommand{\tl}{$1$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача T83. МАКСОР}
\addauthor{Автори: Димитър Шапатов, Кирил Зашев}{2026}{08}{28}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	КОНТРОЛНО СЪСТЕЗАНИЕ\\
	Габрово, 28 август 2026 г.\\
	8 клас
}

Дадено е дърво с $N$ върха. Дефинираме \textit{цена} на пътя между върховете $a$ и $b$ като XOR на ребрата по единствения прост път между тях. Напишете програма \textbf{\texttt{maxor}}, която намира максималната цена на път между два върха от дървото.

\subsection{Вход}
От първия ред на стандартния вход се въвежда естественото число $N$ -- броят върхове в дървото. На всеки от следващите $N-1$ реда се въвеждат по три числа -- $a_i$, $b_i$, $w_i$, които показват, че има ребро между $a_i$ и $b_i$ с тегло $w_i$.

\subsection{Изход}
На единствения ред на стандартния изход се извежда едно число -- отговорът.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
\item $2 \leq N \leq 10^5$
\item $1 \leq a_i, b_i \leq N$
\item $0 \leq w_i < 2^{60}$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
\hline
\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & $w_i$ & \textbf{Други ограничения}\\
\hline
$0$ & $0$ & $-$ & $-$ & Примерният тест. \\
\hline
$1$ & $12$ & $0$ & $< 2^{60}$ & $N \leq 10^3$ \\
\hline
$2$ & $6$ & $-$ & $< 2^{12}$ & \SetCell[r=4]{}{$a_i=i, b_i=i+1$ за $1 \leq i \leq N-1$} \\
\hline
$3$ & $10$ & $2$ & $< 2^{15}$ & \\
\hline
$4$ & $15$ & $2-3$ & $< 2^{20}$ & \\
\hline
$5$ & $12$ & $2-4$ & $< 2^{60}$ & \\
\hline
$6$ & $7$ & $0,2$ & $< 2^{12}$ & \SetCell[r=4]{}{--} \\
\hline
$7$ & $10$ & $0,2-3$ & $< 2^{15}$ & \\
\hline
$8$ & $15$ & $0,2-4$ & $< 2^{20}$ & \\
\hline
$9$ & $13$ & $0-8$ & $< 2^{60}$ & \\
\hline
\end{tblr}
\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\subsection{Пример}
\begin{table}[H]
\begin{tblr}{|l|l|X[j]|}
\hline
\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
\hline
\texttt{\makecell[lt]{6\\
1 2 14\\
2 3 7\\
1 4 22\\
3 5 15\\
4 6 15}}
&
\texttt{\makecell[lt]{31}}
&
Оптималният път е от връх 3 до 4 с цена $7 \oplus 14 \oplus 22 = 31$. \\
\hline
\end{tblr}
\end{table}
\FloatBarrier

\end{document}