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

\begin{document}

\renewcommand{\tl}{$2$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача AT21. ДЖАНКИ}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 27 юни 2026 г.\\
	Група A
}

\indent Сашка има джанково дърво с $N$ върха. Връх $1$ е този, който се намира най-отгоре на дървото и, донякъде контраинтуитивно, ще наричаме корен на дървото.

Във всеки връх, различен от корена, може да расте най-много една групичка джанки. За $j$-тата групичка са дадени върхът $V_j$, в който расте, денят $D_j$, в който джанките в нея стават \emph{идеално узрели} -- нито зелени, нито презрели -- и броят $W_j$ джанки, които Сашка би обрала, ако я откъсне точно тогава.

Беритбата става единствено чрез рязане на клони. В произволен ден Сашка може да отреже колкото иска клони наведнъж; тогава дървото се разпада на части и всяка част, останала без връзка с корена, пада на земята. От всяка такава паднала част Сашка прибира само онези джанки, които са идеално узрели точно на този ден. Джанки, паднали още зелени или останали на дървото до презряване, се похабяват.

Формално, дървото може да се представи като граф-дърво, коренувано във връх $1$ и през всеки ден Сашка може да избере произволно множество от ребра и да ги премахне от дървото. За всяка групичка джанки тя получава стойността $W_j$ тогава и само тогава, когато в ден $D_j$ върхът $V_j$ вече не принадлежи към същата свързана компонента на корена.

Напишете програма \textbf{\texttt{cherryplum}}, която намира максималния общ брой \emph{идеално узрели} джанки, които Сашка може да събере.

\subsection{Детайли по реализацията}
Трябва да предадете файла \texttt{cherryplum.cpp}, който включва \texttt{cherryplum.h} и реализира функцията

\begin{lstlisting}
long long solve(int N, int M, int K, const std::vector<int> &P,
                const std::vector<int> &V, const std::vector<int> &D,
                const std::vector<long long> &W)
\end{lstlisting}

където:

\begin{itemize}
	\item $N$ е броят върхове в дървото;
	\item $M$ е броят групички джанки;
	\item $K$ е последният ден, в който джанки могат да узреят;
	\item $P$ е вектор с $N - 1$ елемента, където $P[i]$ е родителят на връх $i + 2$, т.е. $P[0] = P_2$, $P[1] = P_3$, \dots, $P[N-2] = P_N$;
	\item $V$, $D$ и $W$ са вектори с по $M$ елемента, където $j$-тата групичка расте във връх $V[j]$, узрява в ден $D[j]$ и дава $W[j]$ джанки.
\end{itemize}

Гарантирано е, че стойностите във вектора $V$ са две по две различни.

Функцията се извиква веднъж за всеки тест и трябва да върне едно цяло число -- максималния общ брой \emph{идеално узрели} джанки, които Сашка може да събере.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $2 \leq N \leq 100\ 000$;
	\item $1 \leq M \leq N - 1$;
	\item $1 \leq K \leq 100\ 000$;
	\item $2 \leq V_j \leq N$;
	\item $1 \leq D_j \leq K$;
	\item $1 \leq W_j \leq 10^9$.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & \textbf{Ограничения}\\
		\hline
		$0$ & $0$ & $-$ & Примерът. \\
		\hline
		$1$ & $5$ & $-$ & $N, K \leq 20$ и $W_j = 1$ за всички $j$ \\
		\hline
		$2$ & $3$ & $-$ & Джанките растат само в листа. \\
		\hline
		$3$ & $9$ & $-$ & $P_i = i - 1$ за всяко $i$ и $W_j = 1$ за всички $j$ \\
		\hline
		$4$ & $10$ & $-$ & $K \leq 2$ \\
		\hline
		$5$ & $13$ & $1$ & $K \leq 20$ и $W_j = 1$ за всички $j$ \\
		\hline
		$6$ & $11$ & $0, 1$ & $M \leq 1\ 000$ \\
		\hline
		$7$ & $19$ & $1, 3, 5$ & $W_j = 1$ за всички $j$ \\
		\hline
		$8$ & $30$ & $0 - 7$ & $-$ \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\subsection{Локален грейдър}

Формат на входа:
\begin{itemize}
	\item ред $1$: три цели числа $N\ M\ K$;
	\item редове $2$ до $N$: по едно цяло число на ред -- числата $P_2, P_3, \dots, P_N$;
	\item следващите $M$ реда: по три цели числа $V_j\ D_j\ W_j$ -- описание на групичка джанки.
\end{itemize}

Формат на изхода:
\begin{itemize}
	\item ред $1$: едно цяло число -- върнатата стойност от функцията \texttt{solve}.
\end{itemize}

Форматът на примерите следва формата на локалния грейдър.

\subsection{Пример}

\begin{table}[ht]
	\begin{tblr}{|l|l|}
		\hline
		\textbf{Вход} & \textbf{Изход} \\
		\hline
		\texttt{\makecell[lt]{6 4 10\\1\\2\\1\\4\\4\\3 4 5\\4 7 2\\5 4 1\\6 9 3}} & \texttt{9} \\
		\hline
	\end{tblr}
\end{table}

\subsection{Обяснение на примера}

Едно оптимално решение е следното:

\begin{itemize}
	\item в ден $4$ Сашка реже клона между върхове $4$ и $5$ и събира $1$ джанка от връх $5$, както и клона между върхове $1$ и $2$, с което събира $5$ джанки от връх $3$;
	\item в ден $7$ не прави нищо -- по-изгодно е джанките във връх $4$ да бъдат пожертвани;
	\item в ден $9$ реже клона между върхове $1$ и $4$. Джанките във връх $4$ вече са презрели и се похабяват, но Сашка събира $3$ джанки от връх $6$.
\end{itemize}

Общо Сашка събира $1 + 5 + 3 = 9$ джанки.

\FloatBarrier

\end{document}