Tree

A tree $T = (V, E)$ has $N$ nodes. Each node has one integer written on it, and the integers can be negative. Find two subgraphs $T_a = (V_a, E_a)$ and $T_b = (V_b, E_b)$ of $T$ that satisfy the following conditions.

• $V_a \ne \emptyset$, $V_b \ne \emptyset$
• $T_a$ and $T_b$ are each connected graphs.
• $V_a \cap V_b = \emptyset$
• No edge in $E$ connects a node in $V_a$ with a node in $V_b$.
• The sum of the integers on the nodes in $V_a$ plus the sum of the integers on the nodes in $V_b$ is maximized.

The figure below shows an example. $T = (\{0,1,2,3,4,5,6\}, \{(0, 1), (0,2), (2, 3), (2,4), (4,6), (5,6)\})$.

The number on each node is its node number, and the value inside the node is the integer written on it. Several choices of $T_a$ and $T_b$ satisfy the conditions. Taking $V_a=\{0,2,3\}, V_b=\{5,6\}$ gives the maximum total of $\{3+(-1)+4\} + \{5+3\} = 14$. No other choice gives a value greater than $14$.

You need to write the following function.

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

This function is called exactly once. The input is passed as arguments, and the return value is the answer. $N$ is the number of nodes. The nodes are numbered from $0$ to $N-1$. For $0 \le i \le N-1$, the node numbered $i$ has the value $C[i]$. For $0 \le i \le N-2$, the node numbered $Node1[i]$ and the node numbered $Node2[i]$ are joined by an edge.

• $-10^9 \le C_i \le 10^9$
• $3 \le N \le 500\,000$