Olimpiade Sains Provinsi (OSP) 2023 - Komputer, Nomor 23–25

Untuk menjawab pertanyaan 1 dan 2, perhatikan gambar di bawah ini.

Pak Dengklek berencana untuk membeli oleh-oleh dari kota 2, kota 3, dan kota 4. Diketahui bahwa harga oleh-oleh dari kota 2, kota 3, dan kota 4 secara berturut-turut adalah 2, 3, dan 4 rupiah. Diketahui juga bahwa Pak Dengklek mempunyai anggaran 10 rupiah. Apakah rencana pembelian oleh-oleh tersebut bisa diterapkan? Jawab 0 untuk TIDAK, dan 1 untuk YA.

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Untuk menjawab pertanyaan 1 dan 2, perhatikan gambar di bawah ini.

[Gambar: Pohon (tree graph) dengan 6 node (kota 1-6). Sisi-sisi: 1-2, 1-6, 2-3, 3-4, 2-4, 6-5. Kota 1 di atas, kota 6 di kanan atas, kota 3 di kiri bawah, kota 2 di tengah, kota 4 di bawah, kota 5 di kanan bawah.]

Misalkan Pak Dengklek memiliki anggaran tak terbatas. Ada berapa banyaknya rencana pembelian oleh-oleh berbeda yang bisa diterapkan?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

MEMBELI OLEH-OLEH

Buatlah program menggunakan bahasa C/C++ sesuai deskripsi cerita di atas untuk menentukan maksimum jumlah nilai artefak, dengan ketentuan sebagai berikut:

Format Masukan:
Baris pertama berisi dua buah bilangan: N (banyaknya kota) dan M (anggaran maksimum Pak Dengklek).

Baris kedua berisi N buah bilangan bulat yang menyatakan nilai-nilai A₁, A₂, A₃, …, A_N yaitu harga oleh-oleh dari tiap kota.

N-1 baris selanjutnya menyatakan jalan raya pada Negara Toki. Pada baris ke-i, terdapat dua buah bilangan bulat U_i dan V_i yang menyatakan jalan raya ke-i menghubungi kota U_i dan V_i.

Format Keluaran:
Sebuah baris berisi M buah bilangan bulat. Bilangan ke-K menyatakan banyaknya rencana pembelian oleh-oleh berbeda jika anggaran Pak Dengklek sebesar K rupiah, untuk setiap K dari 1 sampai M.

Contoh Masukan dan Keluaran:

5 10
5 7 2 3 2
1 2
2 3
3 4
4 5

0
2
3
4
7
7
11
12
15
18

6 10
1 2 3 4 5 6
1 2
2 3
2 4
1 6
6 5

1
2
4
6
9
13
15
15
15
15

Penjelasan Contoh:
Pada contoh pertama, jika anggaran Pak Dengklek sebesar 5 rupiah, salah satu contoh rencana pembelian oleh-oleh yang mungkin adalah membeli oleh-oleh dari kota 1. Contoh rencana lain adalah membeli oleh-oleh dari kota 3 dan kota 4. Perhatikan bahwa contoh kasus uji pertama memenuhi Subtask 2.

Batasan:

Untuk semua kasus uji berlaku:

• 2 ≤ N ≤ 100
• 1 ≤ M ≤ 100 000
• 1 ≤ A_i ≤ M
• 1 ≤ U_i, V_i ≤ N
• Dijamin terdapat cara untuk pergi dari setiap kota ke kota lain mana pun melalui satu atau lebih jalan raya.

Subtask 1 (20%)
Subtask ini hanya berisi satu kasus uji, yaitu sebagai berikut:

15 20
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15

Subtask 2 (30%)
Pada subtask ini, dijamin bahwa:

• U_i = i dan V_i = i + 1

Subtask 3 (50%)
Tidak ada batasan tambahan.