시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 348 | 150 | 123 | 49.597% |
수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다.
연산자 노드는 항상 두 개의 자식 노드를 가지며 연산자로 '+
' 또는 '-
' 를 가집니다.
피연산자 노드는 아무 자식도 가지지 않고 하나의 정수를 가집니다.
수식 트리의 계산은 다음과 같이 진행됩니다.
+
' 인 경우, 연산자 노드를 피연산자 노드로 바꾸고 값을 왼쪽 노드의 값과 오른쪽 노드의 값을 더한 값을 가지도록 합니다. 해당 노드의 연산자가 '-
' 인 경우, 연산자 노드를 피연산자 노드로 바꾸고 값을 왼쪽 노드의 값에서 오른쪽 노드의 값을 뺀 값을 가지도록 합니다.위의 과정을 N-1번 진행하면 하나의 수만 남고 이것이 수식의 결과가 됩니다.
진수는 계산을 시작하기 전에 초기 수식 트리의 두 개의 피연산자 노드를 골라 두 피연산자 노드가 가지는 정수를 서로 바꿀 수 있습니다. 오늘 진수가 할 일은 수식 트리가 주어지면 노드에 있는 정수를 원하는 만큼 바꾸어 수식 트리의 결과값이 최대가 되도록 하는 것입니다.
그런데 수식이 너무 큰 나머지 손으로는 계산하기가 힘듭니다. 진수를 도와주세요.
첫 번째 줄에 정수 N (2 ≤ N ≤ 100,000) 이 주어집니다.
다음 N개의 줄에는 1번부터 N번 피연산자 노드가 가지는 정수 ai (-10,000 ≤ ai ≤ 10,000) 가 주어집니다.
그 다음 N-1 개의 줄에는 N+1번 연산자 노드부터 2N-1번 연산자 노드들의 정보가 주어집니다.
각 줄에는 연산자 노드가 가지는 연산자 oi (oi ∈ {'+
', '-
'}) 와 왼쪽 자식 노드의 번호와 오른쪽 자식의 번호 ci,1, ci,2 (1 ≤ ci,1, ci,2 ≤ 2N-2) 가 차례대로 주어집니다.
주어진 입력은 계산이 가능한 올바른 트리임이 보장됩니다.
첫 번째 줄에 피연산자 노드가 가지는 정수들을 바꾸어 만들 수 있는 결과 중 최댓값을 출력합니다.
5 15 20 25 40 50 - 1 2 + 8 5 - 3 4 + 6 7
80
2 -10000 10000 - 1 2
20000
University > 경북대학교 > 2019 Goricon F번