트리
시간 제한2초메모리 제한1024 MB
서로 연결된 두 부분 그래프를 고르되 두 그래프 사이에 간선이 없어야 하며, 노드 값 합의 최댓값을 구한다.
문제
노드가 개 있는 트리 가 있다. 이 트리의 각 노드마다 정수 하나가 쓰여 있다. 음수도 가능하다는 데 유의하라. 우리는 다음 조건을 만족하는 의 두 부분 그래프 와 를 구하려고 한다.
- ,
- 와 는 각각 연결그래프이다.
- 또한 에 속한 노드와 에 속한 노드를 연결하는 에지는 에 없다.
- 마지막으로, 에 속한 노드에 쓰여진 정수들의 합과 에 속한 노드에 쓰여진 정수들의 합을 더한 값이 최대가 되어야 한다.
다음 그림의 예제를 생각해보자. 이다.
노드 위의 숫자는 노드를 나타내는 번호이며, 노드 안의 수가 이 노드에 쓰여진 값이다. 위 조건을 만족하게 와 를 구하는 방법은 여럿이 있을 수 있지만, 으로 잡으면 두 그래프 안에 쓰여진 수의 합이 로 최대가 된다. 다른 방법이 가능하지만 보다 큰 값을 만들 수 없다.
여러분은 다음 함수를 작성하여야 한다.
long long findSum( int N, int C[], int Node1[], int Node2[] );단 한번 호출되는 함 수이다 입력이 인자로 전달되며 이 함수의 리턴값이 문제의 답이다. 은 노드의 개수를 알려준다. 노드들은 번부터 번까지 번호가 붙어 있다. 변수 의 값이 이상 이하 일 때, 번호가 인 노드에 쓰여진 수는 이다. 또, 변수 의 값이 이상 이하일 때, 번호가 인 노드와 번호가 인 노드가 에지로 연결되어 있다.