\documentclass[12pt]{article}
\input{structure_bg.tex}
\fancyhead[R]{
	\begin{minipage}{\textwidth}
		\raggedleft
		\includegraphics[width=2cm]{./logo2.png}
	\end{minipage}
}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}

\renewcommand{\tl}{$0.4$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача OS12. ДЪРВО}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	ОТБОРНО СЪСТЕЗАНИЕ\\
	Габрово, 29 август 2026 г.\\
	8 – 10 клас
}

Дадена е система, която в началото съдържа $N$ върха, номерирани от $1$ до $N$. Връх $i$ има стойност $W_i$ и точно един родител $P_i$. Връх $1$ няма родител.

Системата се променя чрез поредица от $Q$ операции, всяка от които е от един от следните четири вида.
\begin{enumerate}
	\item Добавя се нов връх със стойност $C$ и родител $T$. Неговият номер е $N + t + 1$, където $t$ е броят на върховете, вече добавени чрез операции от този вид; следователно първият добавен по този начин връх получава номер $N + 1$.
	\item Стойността на връх $a$ се променя от $W_a$ на $C$.
	\item Връх $a$ се изтрива завинаги от системата. Гарантирано е, че връх $a$ е листо (няма деца).
	\item При дадено цяло число $X$ трябва да се намери сумата от стойностите на всички върхове, които в момента се намират в системата и са в поддървото на $X$, и освен това са на разстояние $\le H$ от връх $X$, където $H$ е фиксирано за целия вход.
\end{enumerate}

Един връх $B$ се намира в поддървото на някой друг връх $A$ и на разстояние $\le H$, тогава и само тогава когато ако започнем да се движим от връх $B$ по родителите, изминем $\le H$ ребра. 

\subsection{Вход}
От първия ред на стандартния вход се въвеждат три числа $N$, $Q$ и $H$ -- броят върхове в началната система, броят операции и константата $H$ за операциите от вид $4$. От втория ред се въвеждат $N$ числа, $i$-тото от които е $W_i$ -- началната стойност на връх $i$. От третия ред се въвеждат $N - 1$ числа, $i$-тото от които е $P_{i+1}$ -- родителят на връх $i + 1$.

Всеки от следващите $Q$ реда започва с число $t$ -- вида на операцията, последвано от:
\begin{enumerate}
	\item ако $t = 1$: две числа $C$ и $T$ -- стойността и родителя на новия връх;
	\item ако $t = 2$: две числа $a$ и $C$ -- номера на върха, чиято стойност се променя, и новата му стойност;
	\item ако $t = 3$: едно число $a$ -- номера на върха, който сега се премахва от системата;
	\item ако $t = 4$: едно число $X$ -- номера на върха, за който се отнася операцията.
\end{enumerate}

\subsection{Изход}
За всяка операция от вид $t = 4$ изведете на отделен ред търсената сума за системата в актуалното ѝ състояние.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $2 \le N \le 200\,000$
	\item $1 \le Q \le 200\,000$
	\item $1 \le H \le N$
    \item $1 \le P_i < i$
    \item $0 \le W_i \le 10^9$
	\item $0 \le C \le 10^9$, за всяка операция
	\item Гарантирано е, че за всяка операция всички върхове, които участват нея, съществуват в системата в момента на изпълнението ѝ.
	\item Гарантирано е, че никоя операция от вид $t = 3$ не се прилага върху връх $1$.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{\makecell{Необходими\\ подзадачи}} & \textbf{Други ограничения}\\
		\hline
		$0$ & $0$ & $-$ & Примерът. \\
		\hline
		$1$ & $13$ & $0$ & $N, Q \le 5\,000$. \\
		\hline
		$2$ & $11$ & $-$ & $P_i = i - 1$ за всяко $2 \le i \le N$, и всяка операция има $t = 4$. \\
		\hline
		$3$ & $16$ & $-$ & Всяка операция е от вид $t = 4$. \\
		\hline
		$4$ & $10$ & $-$ & $H = 1$. \\
		\hline
		$5$ & $14$ & $-$ & $P_i = i - 1$ за всяко $2 \le i \le N$, и всяка операция е от вид $t = 2$ или $t = 4$. \\
		\hline
		$6$ & $10$ & $-$ & $P_i = \left\lfloor \dfrac{i}{2} \right\rfloor$ за всяко $2 \le i \le N$, и всяка операция е от вид $t = 2$ или $t = 4$. \\
		\hline
		$7$ & $26$ & $0-6$ & Без допълнителни ограничения. \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|}
		\hline
		\textbf{Вход} & \textbf{Изход}  \\
		\hline
		\texttt{\makecell[lt]{8 7 2\\
		10 12 4 20 4 5 11 10\\
		1 1 3 4 2 6 6\\
		1 50 4\\
        4 3\\
        2 1 50\\
        4 1\\
        2 6 35\\
        1 5 7\\
        4 6\\
		}}
		& 
		\texttt{\makecell[lt]{78\\
		91\\
		61\\
		}}
		\\
		\hline
	\end{tblr}
\end{table}

\textbf{Обяснение.} При първата операция от вид $4$ върховете, намиращи се на $\le 2$ разстояние от връх $3$, са $3$, $4$, $9$ и $5$, със стойности съответно $4$, $20$, $50$ и $4$. Затова изведеният отговор е $4 + 20 + 50 + 4 = 78$.

\begin{figure}[H]
	\centering
	\includegraphics[width=0.55\textwidth]{graph-vs1.png}
	\caption*{Начална структура.}
\end{figure}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.55\textwidth]{graph-vs2.png}
	\caption*{Структурата след първата операция.}
\end{figure}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.55\textwidth]{graph-vs3.png}
	\caption*{Структурата след първите три операции.}
\end{figure}

\end{document}
