페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8473
서브태스크

노드 고르기 8s 2048MB

문제

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

번호가 V 인 노드를 잡자.

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

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

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

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

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

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

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


입력

첫 줄에 N 과 K 가 입력된다. ( 1 ≤ N ≤ 40000, 1 ≤ K ≤ N , 1 ≤ K ≤ 3000 )

두 번째 줄에 각 노드를 선택하는 비용 A_1 , A_2, ..., A_N 가 입력된다. ( 각각 50만 이하의 자연수 )

( A_i 는, 번호가 i 인 노드를 선택하는 비용을 의미 )

이후 N - 1 줄에 걸쳐 트리의 간선 정보가 s ~~e 형태로 입력된다.

( 1 ≤ s, e ≤ N , s≠ e )

번호가 s, e 인 두 노드가 연결되어 있다는 뜻이다.

입력되는 간선들은 항상 트리를 이룬다.


출력

V = 1, 2, ..., N 일 때의 정답을 출력한다.


부분문제

번호 점수 조건
#110점

모든 1 ≤ i ≤ N -1 에 대하여,

i 번 노드와 i + 1 번 노드를 잇는 간선이 존재한다.

#220점

K = 3

#330점

1 ≤ N ≤ 500

#440점

제약 조건 없음


예제 #1

5 3
7 4 2 9 5
1 2
2 3
3 4
4 5
13 15 16 16 16

예제 #2

8 5
7 5 9 7 10 9 4 6
1 7
2 5
3 5
4 8
6 1
4 7
1 3
40 40 40 37 40 40 39 33

출처

Petrozavodsk Programming Camp Summer 2022 Day 3 F번
로그인해야 코드를 작성할 수 있어요.