Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTREE - Cây P đỉnh ( Cơ bản )

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/ptree


Cho một cây gồm N đỉnh , mỗi đỉnh có 1 nhãn C[i] gọi là trọng số của đỉnh i . Hãy tìm 1 cây con gồm P đỉnh sao cho tổng trọng số của cây con này là lớn nhất . Hiểu 1 cách đơn giản là tìm P đỉnh sao cho P đỉnh này liên thông và tổng trọng số là lớn nhất .

Vì bài này là ở mức độ khó tuy nhiên lại có nhiều ứng dụng nên các bạn có thể xem lời giải, download test. Nói chung cũng có thể xếp bài này vào nhóm bài “cơ bản” .

Download test và solution tại đây.

Input

Dòng 1 : 2 số nguyên dương N và P . ( 1 ≤ P ≤ N ≤ 200 ) .
Dòng 2 : N số nguyên dương C[1] , … C[N] . ( -1000 ≤ C[i] ≤ 1000 ) .
N – 1 dòng tiếp theo , mỗi dòng gồm 2 số nguyên dương u , v mô tả 1 cạnh của đồ thị .

Output

Gồm 1 dòng ghi ra P số nguyên là chỉ số của P đỉnh được chọn .

Example

Input:
3 2
1 2 3
1 2
2 3

Output:
2 3

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-19
Thời gian chạy:1s
Giới hạn mã nguồn:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Folklore

hide comments
2022-07-14 08:45:02
dễ
2018-11-12 07:23:57
rep to 2017-12-05 04:02:47
bởi vì lúc làm thì mình đi từ 1 -> n
nên khi truy vết phải làm ngược lại là hiển nhiên rồi.
2017-12-07 03:38:55
nhật hào sạch
2017-12-05 04:02:47
Trong code của a Hiếu có 1 chổ rất hack đó là lúc truy vết
for i:=n downto 1 do xét các cạnh kề
sửa lại for i:=1 to n do xét các cạnh kề thì sai :)))
2017-05-25 10:31:26
cách in khó hiểu vc ==
2016-10-24 15:02:30
sao ko tải dc test về vậy
2016-09-27 03:23:36
Code:
http://shink.in/UIBCF
2016-08-26 05:17:05
bài khó vcc

Last edit: 2016-08-26 05:18:05
2016-06-09 11:55:48
2 đấm ac do bố gọi ăn cơm :))~~
2015-09-08 14:16:49
https://thewizard6296.wordpress.com/2015/09/04/5/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.