트리
시간 제한2초메모리 제한1024 MB
각 노드에 정수가 적힌 트리에서 서로 겹치지 않고 간선으로 이어지지 않은 연결된 부분 그래프 두 개를 골라, 노드 값 합의 최댓값을 구합니다.
문제
노드가 개인 트리 가 있다. 각 노드에는 정수가 하나씩 적혀 있으며, 음수일 수도 있다. 다음 조건을 만족하는 의 부분 그래프 와 를 구하려고 한다.
- ,
- 와 는 각각 연결 그래프이다.
- 에 속한 노드와 에 속한 노드를 잇는 간선은 에 없다.
- 에 속한 노드에 적힌 정수의 합과 에 속한 노드에 적힌 정수의 합을 더한 값이 최대가 되어야 한다.
다음 그림이 예시이다. 이다.
노드 위의 숫자는 노드 번호이고, 노드 안의 수가 그 노드에 적힌 값이다. 조건을 만족하는 와 를 고르는 방법은 여럿이다. 으로 잡으면 합이 로 최대가 된다. 다른 방법으로는 보다 큰 값을 만들 수 없다.
구현할 함수
다음 함수를 작성해야 한다.
long long findSum( int N, int C[], int Node1[], int Node2[] );
이 함수는 한 번만 호출된다. 입력은 인자로 전달되며, 함수의 반환값이 문제의 답이다. 은 노드의 개수이다. 노드는 번부터 번까지 번호가 붙어 있다. 일 때 번호가 인 노드에 적힌 수는 이다. 일 때 번호가 인 노드와 번호가 인 노드가 간선으로 연결되어 있다.