\documentclass[12pt]{article}
\input{ejoi_structure_analysis.tex}

\usepackage[bulgarian]{babel}

\begin{document}

\renewcommand{\problemName}{Задача Дърво}

\section{Анализ на задача tree}
\begin{center}
	Решения, условие: Димитър Шапатов; Решения, анализ: Кирил Зашев
\end{center}

Тази задача е класическа encode-decode задача. Ключът към решението се крие във фундаменталното свойство на дърветата: всеки връх има точно един родител, с изключение на корена.

Тогава решението на задачата става тривиално -- избираме си корен на дървото и с DFS намираме родителите на всеки връх. Тъй като ограничението изисква кодиране единствено чрез битове 0 и 1, преобразуваме родителя на всеки връх в двоична бройна система. За да оптимизираме дължината на низа, можем за всеки връх да кодираме само $\left \lfloor{\log_2 N}\right \rfloor + 1$ бита. Декодирането изисква лесна работа с побитови операции.

\end{document}
