17501번 - 수식 트리

수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다.

연산자 노드는 항상 두 개의 자식 노드를 가지며 연산자로 '+' 또는 '-' 를 가집니다.

피연산자 노드는 아무 자식도 가지지 않고 하나의 정수를 가집니다.

수식 트리의 계산은 다음과 같이 진행됩니다.

1. 2개의 피연산자 노드를 자식으로 가지는 연산자 노드를 하나 선택합니다.
2. 해당 노드의 연산자가 '+' 인 경우, 연산자 노드를 피연산자 노드로 바꾸고 값을 왼쪽 노드의 값과 오른쪽 노드의 값을 더한 값을 가지도록 합니다. 해당 노드의 연산자가 '-' 인 경우, 연산자 노드를 피연산자 노드로 바꾸고 값을 왼쪽 노드의 값에서 오른쪽 노드의 값을 뺀 값을 가지도록 합니다.

위의 과정을 N-1번 진행하면 하나의 수만 남고 이것이 수식의 결과가 됩니다.

진수는 계산을 시작하기 전에 초기 수식 트리의 두 개의 피연산자 노드를 골라 두 피연산자 노드가 가지는 정수를 서로 바꿀 수 있습니다. 오늘 진수가 할 일은 수식 트리가 주어지면 노드에 있는 정수를 원하는 만큼 바꾸어 수식 트리의 결과값이 최대가 되도록 하는 것입니다.

그런데 수식이 너무 큰 나머지 손으로는 계산하기가 힘듭니다. 진수를 도와주세요.

첫 번째 줄에 정수 N (2 ≤ N ≤ 100,000) 이 주어집니다.

다음 N개의 줄에는 1번부터 N번 피연산자 노드가 가지는 정수 a_i (-10,000 ≤ a_i ≤ 10,000) 가 주어집니다.

그 다음 N-1 개의 줄에는 N+1번 연산자 노드부터 2N-1번 연산자 노드들의 정보가 주어집니다.

각 줄에는 연산자 노드가 가지는 연산자 o_i (o_i ∈ {'+', '-'}) 와 왼쪽 자식 노드의 번호와 오른쪽 자식의 번호 c_i,1, c_i,2 (1 ≤ c_i,1, c_i,2 ≤ 2N-2) 가 차례대로 주어집니다.

주어진 입력은 계산이 가능한 올바른 트리임이 보장됩니다.

첫 번째 줄에 피연산자 노드가 가지는 정수들을 바꾸어 만들 수 있는 결과 중 최댓값을 출력합니다.