32880번 - 트리 서브태스크언어 제한함수 구현

문제

노드가 $N$개 있는 트리 $T = (V, E)$가 있다. 이 트리의 각 노드마다 정수 하나가 쓰여 있다. 음수도 가능하다는 데 유의하라. 우리는 다음 조건을 만족하는 $T$의 두 부분 그래프 $T_a = (V_a, E_a)$와 $T_b = (V_b, E_b)$를 구하려고 한다.

• $V_a \ne \emptyset,ドル $V_b \ne \emptyset$
• $T_a$와 $T_b$는 각각 연결그래프이다.
• $V_a \cap V_b = \emptyset $
• 또한 $V_a$에 속한 노드와 $V_b$에 속한 노드를 연결하는 에지는 $E$에 없다.
• 마지막으로, $V_a$에 속한 노드에 쓰여진 정수들의 합과 $V_b$에 속한 노드에 쓰여진 정수들의 합을 더한 값이 최대가 되어야 한다.

다음 그림의 예제를 생각해보자. $T = (\{0,1,2,3,4,5,6\}, \{(0, 1), (0,2), (2, 3), (2,4), (4,6), (5,6)\})$ 이다.

노드 위의 숫자는 노드를 나타내는 번호이며, 노드 안의 수가 이 노드에 쓰여진 값이다. 위 조건을 만족하게 $T_a$와 $T_b$를 구하는 방법은 여럿이 있을 수 있지만, $V_a=\{0,2,3\}, V_b=\{5,6\}$으로 잡으면 두 그래프 안에 쓰여진 수의 합이 $\{3+(-1)+4\} + \{5+3\} = 14$로 최대가 된다. 다른 방법이 가능하지만 14ドル$보다 큰 값을 만들 수 없다.

여러분은 다음 함수를 작성하여야 한다.

• long long findSum( int N, int C[], int Node1[], int Node2[] ); 단 한번 호출되는 함 수이다 입력이 인자로 전달되며 이 함수의 리턴값이 문제의 답이다. $N$은 노드의 개수를 알려준다. 노드들은 0ドル$번부터 $N-1$번까지 번호가 붙어 있다. 변수 $i$의 값이 0ドル$ 이상 $N-1$ 이하 일 때, 번호가 $i$인 노드에 쓰여진 수는 $C[i]$이다. 또, 변수 $i$의 값이 0ドル$ 이상 $N-2$ 이하일 때, 번호가 $Node1[i]$인 노드와 번호가 $Node2[i]$인 노드가 에지로 연결되어 있다.

구현 세부사항

여러분은 tree.cpp라는 이름의 정확히 하나의 파일을 제출해야 한다. 이 파일에는 다음의 함수가 구현되어 있어야 한다.

• long long findSum( int N, int C[], int Node1[], int Node2[] );

이 함수는 위에서 설명한 것과 같이 동작하여야 한다 물론 다른 함수들을 만들어서 내부적으로 사용할 수 있다. 제출한 코드는 입출력을 수행하거나 다른 파일에 접근하여서는 안된다.

그레이더 예시

주어지는 그레이더는 다음과 같은 형식으로 입력을 받는다.

• line 1ドル$: $N$
• line 2ドル$: $N$개의 정수 $C_0, C_1, \dots, C_{N-1},ドル 각각 차례로 노드에 쓰인 수이다.
• 다음 $N-1$개의 줄: 2ドル$개의 정수 $a$ $b$. 번호가 $a$인 노드와 번호가 $b$인 노드가 에지로 연결되어 있다.

입력의 한 줄의 마지막 숫자를 표현하는 문자 다음에 빈 칸이나 다른 글자가 있으면 그레이더가 제대로 동작하지 않을 수 있으므로 주의하라.

주어진 그레이더는 여러분의 코드가 findSum() 함수에서 리턴한 값을 출력한다.

입력

출력

제한

• $-10^9 \le C_i \le 10^9$
• 3ドル \le N \le 500,000円$

서브태스크

힌트

첨부

• tree_public.zip