Es gibt einen Baum $T=(V,E)$ mit $N$ Knoten. An jedem Knoten steht eine ganze Zahl; diese darf auch negativ sein. Gesucht sind zwei Teilgraphen $T_a=(V_a,E_a)$ und $T_b=(V_b,E_b)$ von $T$, die folgende Bedingungen erfüllen.

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

• $T_a$ und $T_b$ sind jeweils zusammenhängend.

• $V_a\cap V_b=\varnothing$

• In $E$ gibt es keine Kante zwischen einem Knoten aus $V_a$ und einem Knoten aus $V_b$.

• Die Summe aller Zahlen an Knoten aus $V_a$ und aller Zahlen an Knoten aus $V_b$ soll möglichst groß sein.

Betrachte das Beispiel in der folgenden Abbildung. $T=(\{0,1,2,3,4,5,6\},\{(0,1),(0,2),(2,3),(2,4),(4,6),(5,6)\})$.

Die Zahlen über den Knoten sind ihre Nummern, die Zahlen in den Knoten ihre Werte. Es kann mehrere passende Wahlen von $T_a,T_b$ geben. Mit $V_a=\{0,2,3\}$ und $V_b=\{5,6\}$ erhält man die maximale Summe $\{3+(-1)+4\}+\{5+3\}=14$. Andere Wahlen sind möglich, aber kein Wert größer als $14$.

Implementiere die folgende Funktion.

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

Diese Funktion wird genau einmal aufgerufen. Die Eingabe wird als Argumente übergeben, und der Rückgabewert ist die Antwort. $N$ ist die Anzahl der Knoten, nummeriert von $0$ bis $N-1$. Für $0\le i\le N-1$ ist C[i] die Zahl an Knoten $i$. Für $0\le i\le N-2$ verbindet eine Kante die Knoten Node1[i] und Node2[i].

Implementierungsdetails

Reiche genau eine Datei namens tree.cpp ein, die die folgende Funktion implementiert.

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

Die Funktion muss sich wie oben beschrieben verhalten. Weitere Funktionen für interne Zwecke sind erlaubt. Der eingereichte Code darf keine Ein-/Ausgabe durchführen und nicht auf andere Dateien zugreifen.

Beispiel-Auswertungsprogramm

Das bereitgestellte Auswertungsprogramm liest die Eingabe in folgendem Format.

• Zeile 1: $N$

• Zeile 2: $N$ ganze Zahlen $C_0,C_1,\ldots,C_{N-1}$, die Knotenwerte in dieser Reihenfolge.

• Die nächsten $N-1$ Zeilen: zwei ganze Zahlen $a,b$, die eine Kante zwischen den Knoten $a$ und $b$ angeben.

Beachte: Folgen auf das Zeichen der letzten Ziffer einer Eingabezeile Leerzeichen oder andere Zeichen, funktioniert das Auswertungsprogramm möglicherweise nicht richtig.

Das Auswertungsprogramm gibt den von deiner Funktion findSum() zurückgegebenen Wert aus.

Beschränkungen

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

• $3\le N\le500,000$

Teilaufgaben

1. (7 Punkte) $N\le20$

2. (19 Punkte) $N\le5000$

3. (74 Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

14