수식 트리

수식 트리는 루트가 있는 이진 트리이며 2N-1개의 노드를 가진다. 1번부터 N번까지의 노드는 피연산자 노드이고 나머지 노드는 연산자 노드이며, 2N-1번 노드가 루트이다.

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

피연산자 노드는 자식이 없고 정수 하나를 가진다.

수식 트리를 계산하는 과정은 다음과 같다.

1. 두 개의 피연산자 노드를 자식으로 가지는 연산자 노드를 하나 고른다.
2. 그 노드의 연산자가 '+'이면 연산자 노드를 피연산자 노드로 바꾸고, 왼쪽 노드의 값과 오른쪽 노드의 값을 더한 값을 가지게 한다. 연산자가 '-'이면 연산자 노드를 피연산자 노드로 바꾸고, 왼쪽 노드의 값에서 오른쪽 노드의 값을 뺀 값을 가지게 한다.

이 과정을 N-1번 하면 수 하나가 남고, 이것이 수식의 결과가 된다.

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

그런데 수식이 너무 커서 손으로 계산하기 어렵다. 진수를 도와주자.

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

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

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

각 줄에는 연산자 노드가 가지는 연산자 oᵢ (oᵢ ∈ {'+', '-'})와 왼쪽 자식 노드의 번호, 오른쪽 자식 노드의 번호 cᵢ,₁, cᵢ,₂ (1 ≤ cᵢ,₁, cᵢ,₂ ≤ 2N-2)가 차례로 주어진다.

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

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