선거 운동 (Election Exercise)

문제

인덱스국 도로교통 : Day 4

인덱스국의 국왕 선거는 찬반 투표로 이루어집니다. 물론 반대에 투표할 경우 즉결심판으로 사형에 처해지기 때문에 출구조사에 의하면 반대에 투표한 사람은 없습니다. 인덱스국의 국왕이자 국왕 후보인 (검열됨)은 명색이 선거인데 선거 운동 정도는 해야하지 않을까 싶어서 선거 운동 일정을 세우기로 하였습니다.

인덱스국은 N개의 도시와 두 도시를 연결하는 N − 1개의 도로로 이루어져 있으며, 임의의 두 도시에 대해서 두 도시 사이를 도로를 이용하여 이동할 수 있습니다. 각각의 도시에는 1부터 N까지의 번호가 매겨져 있는데, (검열됨)은 하나의 도시를 골라 그 도시에 선거 운동 본부를 설치하려고 합니다. v번 도시에 선거 운동 본부를 설치한 후, (검열됨)은 v번 도시를 루트로 하는 트리 모양으로 인덱스국의 지도를 그리기로 했습니다. (검열됨)은 다음과 같은 방법을 따라 선거 운동을 진행하려고 합니다.

• (검열됨)은 어떤 도시에 처음으로 방문할 때마다 해당 도시에서 연설을 합니다.
• (검열됨)이 a번 도시에 방문했을 경우, a번 도시의 서브트리에 있는 모든 도시를 방문하기 전까지 a번 도시의 서브트리에서 나오지 않습니다.

각 도시 $i$에는 지지율 $a_i$가 정해져 있고, $i$번 도시가 (검열됨)이 $j$번째로 연설한 도시일 경우 $\text{ord}_i = j$입니다. (당연히 $\text{ord}_v = 1$입니다.) 인덱스국 통계청에 의하면, 선거 운동의 효과는 $\sum_{i=1}^{N} a_i \times \text{ord}_i$로 계산됩니다.

(검열됨)은 선거 운동의 전체 효과를 최대화하려고 합니다. 물론, 선거 본부 v는 정해져 있지 않으니, 가능한 모든 경우를 고려해 보아야 합니다. 사형에 처해지는 인원의 수를 최대한 줄이기 위해서, 당신은 선거 운동의 효과를 최대화하기 위한 전략을 짜는 프로그램을 작성하려고 합니다.

구현 세부 사항

다음 함수를 구현하세요.

int64 getElectionEffect(int A[], int S[], int E[])

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.

• S, E는 크기 N − 1의 배열입니다. 모든 0 ≤ i ≤ N − 2에 대해 S[i]번 도시와 E[i]번 도시를 연결하는 도로가 존재합니다.

• A는 크기 N의 배열입니다. 모든 0 ≤ i ≤ N − 1에 대해 i + 1번 도시의 지지율 $a_{i+1}$ = A[i] 입니다.

• 이 함수는 최대 선거 운동의 효과를 반환해야 합니다.

제한 조건

• 1 ≤ N ≤ 200,000
• $−10^8$ ≤ A[i] ≤ $10^8$ (0 ≤ i ≤ N − 1)
• 1 ≤ S[i], E[i] ≤ N (0 ≤ i ≤ N − 2)

서브태스크

서브태스크	점수	제한 조건
1	2	N ≤ 10
2	6	N ≤ 2000
3	3	1번 정점에서 시작했을 때, 최적인 경로 존재
4	4	추가 제한 조건 없음

예제 입출력

N = 6, A = [2, 3, −9, 0, 5, −7], S = [3, 4, 1, 2, 1], E = [2, 6, 6, 5, 2]

그레이더는 다음 함수를 호출합니다.

getElectionEffect([2, 3, −9, 0, 5, −7], [3, 4, 1, 2, 1], [2, 6, 6, 5, 2]) = 5

샘플 그레이더

샘플 그레이더는 다음의 형식으로 입력을 받습니다.

• line 1 : N
• line 2 : A[0] A[1] ··· A[N − 1]
• line 3 + i (0 ≤ i ≤ N − 2) : S[i] E[i]