% !TEX program = lualatex % (can also use "xelatex") 
\documentclass[12pt]{article}
\input{ejoi_structure.tex}

\usepackage[bulgarian]{babel}
    
\begin{document}

\renewcommand{\round}{Ден 0}
\renewcommand{\problemName}{Задача Дърво 2}
\renewcommand{\lang}{Български}

\renewcommand{\tl}{$1.0$ sec.}
\renewcommand{\ml}{$256$ MB} 
\problem{\problemName}
Алиса отново си е намислила дърво с $N$ върха, номерата на някои от които тя ще изтрие. Тя ще играе с Боби, който ще се опита да възстанови оригиналното дърво със своите номера на върховете, използвайки новото дърво на Алиса, като преди това те са се разбрали за стратегията, която ще използват. Вашата цел е да имплементирате стратегия за двамата, която изтрива максимален брой номера на върхове.

\subsection{Детайли по имплементацията}
Трябва да имплементирате следните функции, които ще бъдат извикани в \textbf{отделни} процеси:
\begin{lstlisting}
std::vector<int> encode(int N, std::vector<std::pair<int, int>> v);
\end{lstlisting}
Тази функция реализира стратегията на Алиса. Тя се извиква веднъж от журито и като параметър се подават броят върхове и двупосочните ребра $(x,y)$, описващи дървото. Трябва да върне номерата на върховете, които тя ще изтрие.
\begin{lstlisting}
std::vector<std::pair<int, int>> decode(int N, std::vector<std::pair<int, int>> v);
\end{lstlisting}
Тази функция реализира стратегията на Боби. Тя се извиква веднъж от журито и като параметър се подават броят върхове и двупосочните ребра $(x,y)$ в новото дърво на Алиса. Възможно е журито да е разменило реда на върховете в някои ребра, \textbf{но не и реда на самите ребра}. Номерът на всеки връх от оригиналното дърво, който е изтрит от Алиса, е заместен с ново, отрицателно число от $-N$ до $-1$, като новите номера на никои два върха не съвпадат. Функцията трябва да върне оригиналното дърво, описано с оригиналните двупосочни ребра и оригиналните номера на върховете. Няма значение редът на ребрата, както и на върховете в тях.

\textbf{Новите номера на всички изтрити върхове са на случаен, детерминистичен принцип, с изключение на връх 1. Ако той е изтрит, в новото дърво винаги има номер -1!}

\subsection{Ограничения}
\begin{itemize}
\item $1 \leq N \leq 65536$
\end{itemize}

\subsection{Оценяване}
Нека $S$ е броят номера на върхове, изтрити от Алиса. Тогава $points=\min(\frac{S}{\lfloor \sqrt{N} \rfloor}, 1)$.

\subsection{Подзадачи}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|}
\hline
\textbf{Подзадача} & \textbf{Точки} & \textbf{Допълнителни ограничения}\\
\hline
$0$ & $0$ & Примерът.\\
\hline
$1$ & $50$ & $N=256$\\
\hline
$2$ & $50$ & $N=65536$\\
\hline
\end{tblr}
\caption*{Ако всички тестове в една подзадача са верни, точките се определят като сумарната вярност на тестовете.}
\end{table}
\FloatBarrier

\subsection{Пример}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|}
\hline
\textbf{Жури} & \textbf{Състезател}\\
\hline
\texttt{encode(3, \{\{1, 2\}, \{2, 3\}\})} & \texttt{\{2\}}\\
\hline
\texttt{decode(3, \{\{1, -1\}, \{-1, 3\}\})} & \texttt{\{\{1, 2\}, \{2, 3\}\}}\\
\hline
\end{tblr}
\end{table}

\subsection{Примерен грейдър}
На първия ред се въвежда числото $N$. На следващите $N-1$ реда се въвеждат ребрата $(x, y)$.

\end{document}


