\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}

\renewcommand{\tl}{$1$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача C2. Мениджърски хаос}
\addauthor{Автор: Румен Михов}{2025}{11}{22}
\renewcommand{\header}{
	НАЦИОНАЛЕН ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА\\
	София, 21 – 23 ноември 2025 г.\\
	Група C – 7, 8 клас
}

В една голяма компания организационната структура е представена като кореново дърво с $N$ служители, номерирани от $1$ до $N$. Главният изпълнителен директор (CEO) е служител~$1$ и той е коренът на дървото. Всеки служител има точно един пряк мениджър, освен главният изпълнителен директор.

Казваме, че $u$ e косвен мениджър на $v$, ако съществуват служители $v = m_1, m_2, \dots, m_k = u$, $k \geq 2$, където $m_{i+1}$ е пряк мениджър на $m_i$ в йерархията за $i = 1, 2, \dots, k-1$. Да отбележим, че прекия мениджър на $u$ също се явява и косвен такъв.
 
След задълбочен анализ, управата планира да извърши $Q$ повишения. За $i$-тото повишение, управата е избрала служител $c_i$ и негов косвен мениджър $p_i$, който след повишението да стане пряк мениджър на $c_i$. За да няма сърдити служители, управата решила да повиши и всички мениджъри, които се намират по верижката от $c_i$ до $p_i$ и те също да получат за пряк мениджър $p_i$. 

По-формално, нека $c_i = m_1, m_2, \dots, m_k = p_i$ е редицата от преки мениджъри от $c_i$ до $p_i$. Тогава след повишението $m_1, m_2, \dots m_{k-1}$ ще получат за пряк мениджър $p_i$. В случай, че $k=2$ всички запазват своя пряк мениджър.

Сега управата се зачудила как тези повишения ще повлияят на трудността на комуникация във фирмата. По-точно, след всяко от тези $Q$ повишения, за всеки служител разглеждат броя на косвените му мениджъри и като оценка за трудността на комуникация, определят сумата на този брой за всички служители. 

След дълги спорове, кой да бъде повишен, не останало време да пресметнат оценката за трудността на комуникация, затова сега ви молят за помощ. Напишете програма \textbf{\texttt{managers}}, която по дадена начална йерархия във фирмата и $Q$ повишения, намира след всяко повишение оценката за трудността на комуникацията. 

\subsection{Вход}
На първия ред на стандартния вход се въвеждат две числа -- $N$, $Q$ -- броят служители и броят повишения съответно.
Следват $N-1$ реда, всеки с по две числа -- $u_j$ и $v_j$ -- указващи, че $u_j$ е пряк мениджър на $v_j$ в първоначалната йерархия.
На всеки от последните $Q$ реда има по две числа -- $p_i$ и $c_i$ -- означаващи, че след повишението $p_i$ ще стане пряк мениджър на $c_i$.

\subsection{Изход}
На стандартния изход изведете $Q$ реда, всеки с по едно число, $i$-тото от които е оценката за трудността на комуникация във фирмата след $i$-тото повишение.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq N, Q \leq 10^5$;
	\item $1 \leq u_j,v_j,p_i,c_i \leq N$; 
	
\end{itemize}
Гарантирано е, че началната йерархия образува дърво с корен $1$. \\
Гарантирано е, че в момента на $i$-тото повишение, $p_i$ e косвен мениджър на $c_i$.

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m, wd=8cm]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & \textbf{Допълнителни ограничения}\\
		\hline
		$1$ & $5$ & $-$ & $N \leq 1000, Q = 1$  \\ 
		\hline
		$2$ & $16$ & $1$ & $N*Q \leq 10^7$ \\ 
		\hline
		$3$ & $25$ & $-$ & Всички служители с изключение на един имат по точно един пряк подчинен, т.е йерархията образува пръчка.\\
		\hline
		$4$ & $21$ & $-$ & За всяко повишение $p_i$,$c_i$, $p_i$ е прекия мениджър на $c_i$ или $p_i$ е прекия мениджър на прекия мениджър на $c_i$.\\
		\hline
		$5$ & $33$ & $1-4$ & $-$ \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\subsection{Примери} 
\begin{table}[ht] 
\begin{tblr}{
    colspec = {|Q[l,h,wd=0.08\linewidth]|
                Q[l,h,wd=0.08\linewidth]|
                X[j,h,wd=0.78\linewidth]|},
    rows    = {valign=h},
    hlines,
}
    \textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера}\\ 

    % КОЛОНА 1 – многоредов вход
    \texttt{%
      9 4 \\
      1 2 \\
      1 3 \\
      3 4 \\
      3 5 \\
      4 6 \\
      4 7 \\
      5 8 \\
      8 9 \\
      1 3 \\
      1 4 \\
      1 8 \\
      1 7
    }
    &
    % КОЛОНА 2 – многоредов изход
    \texttt{%
      19 \\
      16 \\
      11 \\
      10
    }
    &
    % КОЛОНА 3 – ВЛОЖЕНА ТАБЛИЦА, ОПАКОВАНА В PARBOX[t]
    \parbox[t]{\linewidth}{%
      \begin{tblr}{
        colspec = {X[c] X[c] X[c]},
        width   = \linewidth,
        rowsep  = 10pt,              
        colsep  = 3pt,
        row{2,4} = {font=\footnotesize},
      }
        % Row 1: Images (примерно – може да сложиш svg)
        \includesvg[scale=0.5, inkscapelatex=false]{graph1} & 
        \includesvg[scale=0.5, inkscapelatex=false]{graph1} & 
        \includesvg[scale=0.5, inkscapelatex=false]{graph2} \\
        % Row 2: Captions
        Начална йерархия & след първото повишение & след второто повишение \\
        % Row 3: Images
        \includesvg[scale=0.5, inkscapelatex=false]{graph3} & 
        \includesvg[scale=0.5, inkscapelatex=false]{graph4} & 
        \\ 
        % Row 4: Captions
        след третото повишение & след четвъртото повишение & 
      \end{tblr}
    }
    \\
  \end{tblr} 
\end{table}


\end{document}
