Dane jest drzewo $T=(V,E)$ o $N$ wierzchołkach. Na każdym zapisano liczbę całkowitą, która może być ujemna. Szukamy dwóch podgrafów $T_a=(V_a,E_a)$ i $T_b=(V_b,E_b)$ drzewa $T$, spełniających poniższe warunki.

• $V_a\ne\varnothing,\quad V_b\ne\varnothing$

• $T_a$ i $T_b$ są spójne.

• $V_a\cap V_b=\varnothing$

• W $E$ nie ma krawędzi łączącej wierzchołek z $V_a$ z wierzchołkiem z $V_b$.

• Suma liczb zapisanych na wierzchołkach $V_a$ oraz liczb zapisanych na wierzchołkach $V_b$ ma być jak największa.

Rozważmy przykład na poniższym rysunku. $T=(\{0,1,2,3,4,5,6\},\{(0,1),(0,2),(2,3),(2,4),(4,6),(5,6)\})$.

Liczby nad wierzchołkami są ich numerami, a liczby wewnątrz — ich wartościami. Może istnieć wiele wyborów $T_a,T_b$ spełniających warunki. Wybór $V_a=\{0,2,3\}$ i $V_b=\{5,6\}$ daje maksymalną sumę $\{3+(-1)+4\}+\{5+3\}=14$. Możliwe są inne wybory, lecz nie da się uzyskać wartości większej niż $14$.

Zaimplementuj poniższą funkcję.

long long findSum( int N, int C[], int Node1[], int Node2[] );

Funkcja zostanie wywołana dokładnie raz. Dane są przekazywane argumentami, a wartość zwracana jest odpowiedzią. $N$ oznacza liczbę wierzchołków, numerowanych od $0$ do $N-1$. Dla $0\le i\le N-1$ C[i] jest liczbą zapisaną w wierzchołku $i$. Dla $0\le i\le N-2$ wierzchołki Node1[i] i Node2[i] są połączone krawędzią.

Szczegóły implementacji

Prześlij dokładnie jeden plik o nazwie tree.cpp, zawierający implementację poniższej funkcji.

long long findSum( int N, int C[], int Node1[], int Node2[] );

Funkcja powinna działać zgodnie z powyższym opisem. Możesz definiować inne funkcje do użytku wewnętrznego. Przesłany kod nie może wykonywać operacji wejścia/wyjścia ani uzyskiwać dostępu do innych plików.

Przykładowy program oceniający

Dostarczony program oceniający czyta dane w następującym formacie.

• Wiersz 1: $N$

• Wiersz 2: $N$ liczb całkowitych $C_0,C_1,\ldots,C_{N-1}$, kolejno wartości wierzchołków.

• Następne $N-1$ wierszy: dwie liczby całkowite $a,b$ oznaczające krawędź między wierzchołkami $a$ i $b$.

Uwaga: jeśli po znaku ostatniej cyfry w wierszu wejścia występują spacje lub inne znaki, program oceniający może nie działać poprawnie.

Program oceniający wypisuje wartość zwróconą przez funkcję findSum().

Ograniczenia

• $-10^9\le C_i\le10^9$

• $3\le N\le500,000$

Podzadania

1. (7 punktów) $N\le20$

2. (19 punktów) $N\le5000$

3. (74 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

7
3 -5 -1 4 2 5 3
0 1
0 2
2 3
2 4
4 6
5 6

Wyjście 1

14