The Parity Pendulum

Find the maximum sum of values along a downward path (starting at any node and only moving to descendants) such that the parity of the node values alternates (Even-Odd-Even or Odd-Even-Odd). Input Format: - Line 1: N (number of nodes). - Line 2: N integers (values of nodes 0 to N-1). - Next N-1 lines: Two integers u and v (u is parent of v). Output Format: - The maximum sum of an alternating parity downward path. Example: Input: 4 2 3 4 5 0 1 1 2 2 3 Output: 9 Explanation: Path 0->1->2 is 2(E), 3(O), 4(E). Sum = 9. Path 1->2->3 is 3(O), 4(E), 5(O). Sum = 12. Max is 12.