Tetonun Emosiyaları

Giriş

Birinci sətirdə bir tam ədəd $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5) — mahnıdakı fraqmentlərin sayı verilir.

İkinci sətirdə $n$ tam ədəd $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ (-10^9 \le a_i \le 10^9) — fraqmentlərin emosional dəyərləri verilir.

Növbəti $n - 1$ n-1 sətrin hər birində iki tam ədəd $u$ və $v$ $(1 \leq u, v \leq n, u \neq = v)$ (1 \le u, v \le n,\ u \ne v) — ağacın bir kənarı verilir.

Verilmiş qrafın ağac olduğuna zəmanət verilir.

Çıxış

Bir tam ədəd çıxarın — mərkəzi fraqment $v$ -nin bütün mümkün seçimləri arasında maksimum mümkün kontrast.

Nümunələr

Nümunə 1

Loading

Nümunə 2

Loading

Qeyd

Birinci nümunədə mərkəzi fraqment kimi $v = 4$ v = 4 seçmək optimaldır. Bu zaman $2$ -ci fraqment ondan məsafəsi düz $2$ olduğu üçün silinir.

Silinmədən sonra iki bağlı hissə qalır:

${1}$ , cəmi $1$ ;
${3, 4, 5}$ \{3, 4, 5\}, cəmi $3 + 4 + 5 = 12$ 3 + 4 + 5 = 12.

Beləliklə, kontrast $12 - 1 = 11$ 12 - 1 = 11 olur.

İkinci nümunədə mərkəzi fraqment kimi $v = 2$ v = 2 seçmək optimaldır. Bu zaman $3$ -cü fraqment ondan məsafəsi düz $2$ olduğu üçün silinir.

Silinmədən sonra üç bağlı hissə qalır:

${1, 2, 4, 5}$ \{1, 2, 4, 5\}, cəmi $5 + (- 2) + 10 + (- 3) = 10$ 5 + (-2) + 10 + (-3) = 10;
${6}$ , cəmi $7$ ;
${7}$ , cəmi $- 6$ .

Beləliklə, kontrast $10 - (- 6) = 16$ 10 - (-6) = 16 olur.

Bal hesablama

Alt tapşırıq $1$ ( $10$ bal): $n \leq 10$ n \le 10.
Alt tapşırıq $2$ ( $30$ bal): $n \leq 5000$ n \le 5000.
Alt tapşırıq $3$ ( $30$ bal): ağac bir yoldur.
Alt tapşırıq $4$ ( $30$ bal): bütün $1 \leq i \leq n$ 1 \le i \le n üçün $a_{i} = 1$ a_i = 1.
Alt tapşırıq $5$ ( $40$ bal): bütün $1 \leq i \leq n$ 1 \le i \le n üçün $∣ a_{i} ∣ \leq 1$ |a_i| \le 1.
Alt tapşırıq $6$ ( $40$ bal): bütün $1 \leq i \leq n$ 1 \le i \le n üçün $a_{i} \geq 0$ a_i \ge 0.
Alt tapşırıq $7$ ( $120$ bal): Əlavə məhdudiyyət yoxdur.