% !TeX program=lualatex

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

\begin{document}

\renewcommand{\tl}{$0.1$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача CT1. ПЛАНИНА}
\addauthor{Автор: Петър Петров (заета)}{2030}{12}{20}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 2 май 2026 г.\\
	Група C, 7 -- 8 клас
}

В планински район има $n$ важни точки -- хижи, върхове и проходи. Някои двойки точки са свързани с маршрути. Известно е, че всички точки и маршрути образуват дърво.

Всяка точка има цяло число $d_i$, което описва нейната опасност. Колкото по-голямо е числото, толкова по-трудна и опасна е точката.

Поради очаквани тежки метеорологични условия планинската спасителна служба трябва да затвори всички маршрути, така че всяка точка да остане изолирана.

Когато се затвори един маршрут, текущата свързана област се разделя на две независими области. За всяка такава област спасителните екипи трябва да бъдат подготвени за най-опасната точка в нея. Затова цената на затваряне на маршрута е равна на сумата от максималните опасности в двете получени области.

По-точно, ако след затваряне на маршрут се получат две компоненти $A$ и $B$, цената е:
\[
	\max_{v \in A} d_v + \max_{v \in B} d_v.
\]

Редът, в който се затварят маршрутите, може да влияе на общата цена.

Напишете програма \texttt{\textbf{mountain.cpp}}, която намира минималната възможна обща цена за затваряне на всички маршрути.

\subsection{Вход}
От първия ред на стандартния вход се въвежда $n$ -- броят на точките.

От втория ред се въвеждат $n$ цели числа $d_1, d_2, \ldots, d_n$ -- опасностите на точките.

Всеки от следващите $n - 1$ реда съдържа по две цели числа $x$ и $y$, означаващи, че между точките $x$ и $y$ има маршрут.

\subsection{Изход}
На първия ред на стандартния изход изведете едно цяло число -- минималната възможна обща цена за затваряне на всички маршрути.
 
\subsection{Ограничения}
\begin{itemize}
	\item $1 \leq n \leq 100~000$
	\item $1 \leq d_i \leq 10^9$
	\item $1 \leq x, y \leq n$
	\item Даденият граф е дърво.
\end{itemize}
\FloatBarrier

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & $n$ & \textbf{Други ограничения}\\
		\hline
		$1$ & $0$ & $-$ & Примерите от условието. \\
		\hline
		$2$ & $10$ & $\le 10$ & -- \\
		\hline
		$3$ & $20$ & $\le 100~000$ & Точките $i$ и $i+1$ са директно свързани за всяко $1 \le i < n$. \\
		\hline
		$4$ & $25$ & $\le 1000$ & -- \\
		\hline
		$5$ & $45$ & $\le 100~000$ & -- \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
\end{table}
\FloatBarrier

\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{width=\linewidth, colspec={|X[l]|X[l]|}}
		\hline
		\textbf{Вход 1} & \textbf{Изход 1} \\
		\hline
		\texttt{\makecell[lt]{3\\1 2 3\\1 2\\2 3}} & \texttt{8} \\
		\hline
		\textbf{Вход 2} & \textbf{Изход 2} \\
		\hline
		\texttt{\makecell[lt]{4\\2 2 3 2\\1 3\\3 2\\4 3}} & \texttt{15} \\
		\hline
		\textbf{Вход 3} & \textbf{Изход 3} \\
		\hline
		\texttt{\makecell[lt]{5\\5 2 3 1 4\\2 1\\3 1\\2 4\\2 5}} & \texttt{26} \\
		\hline
	\end{tblr}
\end{table}

\subsection{Обяснение на пример 1}
Имаме три точки с опасности $1$, $2$ и $3$.

Ако първо затворим маршрута между точки $1$ и $2$, получаваме компоненти с максимални опасности $1$ и $3$, следователно цената е $1 + 3 = 4$.

След това затваряме маршрута между точки $2$ и $3$, цената е $2 + 3 = 5$. Общата цена е $9$.

По-добре е първо да затворим маршрута между точки $2$ и $3$. Тогава цената е $2 + 3 = 5$.

След това затваряме маршрута между точки $1$ и $2$, като компонентите имат максимални опасности $1$ и $2$, следователно цената е $1 + 2 = 3$.

Общата цена е $5 + 3 = 8$, което е минималният възможен резултат.

\end{document}