트리

노드가 $N$개 있는 트리 $T = (V, E)$가 있다. 이 트리의 각 노드마다 정수 하나가 쓰여 있다. 음수도 가능하다는 데 유의하라. 우리는 다음 조건을 만족하는 $T$의 두 부분 그래프 $T_a = (V_a, E_a)$와 $T_b = (V_b, E_b)$를 구하려고 한다.

• $V_a \ne \emptyset$, $V_b \ne \emptyset$
• $T_a$와 $T_b$는 각각 연결그래프이다.
• $V_a \cap V_b = \emptyset $
• 또한 $V_a$에 속한 노드와 $V_b$에 속한 노드를 연결하는 에지는 $E$에 없다.
• 마지막으로, $V_a$에 속한 노드에 쓰여진 정수들의 합과 $V_b$에 속한 노드에 쓰여진 정수들의 합을 더한 값이 최대가 되어야 한다.

다음 그림의 예제를 생각해보자. $T = (\{0,1,2,3,4,5,6\}, \{(0, 1), (0,2), (2, 3), (2,4), (4,6), (5,6)\})$ 이다.

노드 위의 숫자는 노드를 나타내는 번호이며, 노드 안의 수가 이 노드에 쓰여진 값이다. 위 조건을 만족하게 $T_a$와 $T_b$를 구하는 방법은 여럿이 있을 수 있지만, $V_a=\{0,2,3\}, V_b=\{5,6\}$으로 잡으면 두 그래프 안에 쓰여진 수의 합이 $\{3+(-1)+4\} + \{5+3\} = 14$로 최대가 된다. 다른 방법이 가능하지만 $14$보다 큰 값을 만들 수 없다.

여러분은 다음 함수를 작성하여야 한다.

• long long findSum( int N, int C[], int Node1[], int Node2[] ); 단 한번 호출되는 함 수이다 입력이 인자로 전달되며 이 함수의 리턴값이 문제의 답이다. $N$은 노드의 개수를 알려준다. 노드들은 $0$번부터 $N-1$번까지 번호가 붙어 있다. 변수 $i$의 값이 $0$ 이상 $N-1$ 이하 일 때, 번호가 $i$인 노드에 쓰여진 수는 $C[i]$이다. 또, 변수 $i$의 값이 $0$ 이상 $N-2$ 이하일 때, 번호가 $Node1[i]$인 노드와 번호가 $Node2[i]$인 노드가 에지로 연결되어 있다.

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