頁面無法載入？點擊這裡可能會修復。
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번
需要登入才能撰寫程式碼。