N 개의 노드로 구성된 트리가 있고, 노드들에는 각각 1 ~ N 의 번호가 매겨져 있다.

번호가 V 인 노드를 잡자.

우리는 V 를 포함하여 K 개의 노드들을 선택해야 한다.

단, 선택된 K 개의 노드들만 따졌을 때, 반드시 연결 그래프가 되어야 한다.

다시 말해, 원본 트리에서 선택되지 않은 N - K 개의 정점을 지우면, 남아 있는 그래프가 연결 그래프가 되어야 한다는 것이다.

이 조건을 만족하는 K 개의 노드를 고르는 방법은 여러 가지다.

각 노드를 선택하는 비용 A_i ( 1≤ i ≤ N ) 이 주어질 때,

각 V = 1, 2, ..., N 에 대하여,

조건을 만족하며 K 개의 노드를 선택하는 최대 비용을 구하자.

노드 고르기 timer 8s memory 2048MB

노드 고르기 8s 2048MB