# Editorial Simulasi OSN 2022 - 2B
## by kokocoder (unofficial)

---

<center><h3>Soal 2B</h3></center>

**Observasi 1 :**
(dapet dari subtask yang isinya semua jalur kereta)
Jalur kereta sebenernya bisa connect antar 2 node dengan cost gratis (gak perlu tiket pesawat)

Artinya, node yang terhubung oleh jalur kereta (langsung ataupun enggak), bisa kita jadiin satu connected component (pake DSU)

Yaudah disini kita bisa definisiin **component** adalah kumpulan node node yang terconnect sama jalur kereta api


**Lemma 1**
Karena suatu node dikatakan spesial kalo dia bisa visit semua node lainnya, maka kalo semua jalur merupakan jalur kereta, suatu node bisa dikatakan spesial kalo semua node terhubung dalam satu component

Jadi jawaban buat subtask yang semuanya jalur kereta :

- Kalo semua node terconnect, berarti jawabannya `0 0 0 ... 0`
- Kalo nggak, berarti jawabannya : `-1 -1 ... -1`

---

**Observasi 2**
Node yang berada dalam satu component bisa menuju satu sama lain dengan gratis (karena semua terconnect sama jalur kereta)

**Lemma 2**
Itu berarti, **jalur pesawat yang menghubungkan 2 node di component yang sama sebenernya gak guna** ~~kayak mengejar gebetan yang cintanya tidak berbalas~~ soalnya dia bisa pergi dari node itu ke node satunya pake jalur kereta doang (gratis)

Contoh disini edge (1,3) dan (4,7) itu gak guna. Soalnya dari 1 -> 3 bisa lewat rute 1 -> 2 -> 3, dan dari 7 -> 4 bisa lewat rute 7 -> 5 -> 4

Jadi dari sini, kita bisa abaikan jalur jalur pesawat yang gak guna ini

---

**Observasi 3**
(buat subtask yang isinya semua edge pesawat yang bobotnya sama)
Dari semua jalur kereta yang tersisa, pasti jalur ini menghubungkan 2 connected component berbeda

Jadi sekarang kita punya pertanyaan :
*Kapan suatu node dikatakan "spesial"?*

Coba kita liat gambar di bawah ini


Disini kita bissa dapet satu observasi bahwa :
suatu node dikatakan spesial kalo dia bisa pergi ke semua node lainnya dengan melewati **maksimal** satu edge pesawat (berapapun cost nya)

Contohnya disini node 8 semuanya spesial soalnya dia bisa pergi ke semua node lainnya

Tapi node 4 gak spesial soalnya dia gak bisa visit node 1, 2, sama 3

Dari sini kita bisa liat kalo
Kespesialan suatu node yang berada dalem satu DSU / component itu sama

Misalnya kalo 8 spesial, berarti semua node yang satu grup sama 8 ya spesial semua (9, 10, 11, 12)

Sebaliknya, misalnya node 4 gak spesial, berarti node 5, 6, 7 juga gak spesial

~~kalo kamu di hatiku spesial~~

**Lemma 3**

Suatu grup dikatakan spesial kalo ada edge yang ngehubungin grup itu dengan semua grup lainnya

Misalnya di gambar diatas, grup hijau (grup nomor 2) itu spesial soalnya dia terconnect sama grup ungu (grup nomor 1) lewat edge (8,3) atau (10,3)

Selain itu dia juga terconnect sama grup biru (grup nomor 3) lewat edge (12, 4) atau (11, 6)

--

Sebaliknya, grup biru (grup nomor 3) gak spesial karena gak ada edge yang mengconnect grup biru (grup 3) sama ungu (grup 1)

Itu kenapa di subtask yang semua weight edge nya sama, kita bisa ngelakuin gini :

Cari grup mana aja yang spesial (dari **lemma 3**), terus jumlahin semua size dari grup spesial ini. Berarti kita punya node spesial sebanyak $S = size_1 + size_2 + ... + size_K$ dimana $size_i$ adalah ukuran dari grup spesial ke $i$

Jadi nanti jawabannya tinggal kayak
`W W W ...` sebanyak ($S$ kali) -> banyak node spesial ada $S$
`-1 -1 -1 ...` sebanyak ($N - S$ kali) -> banyak node tidak spesial ada $N-S$

---

**Observasi 4**
(dapet dari subtask yang $W$ nya semua edge pesawat beda semua)

Kalo ada banyak edge pesawat yang menghubungkan dua grup yang sama, kita cukup ambil edge yang $W$ nya paling kecil (soalnya kita mau lewatin rute pesawat yang paling murah)


Misalnya ada edge 10 sama 5 kayak gini, maka lebih efektif kalo kita ambil yang 5, sedangkan yang 10 kita abaikan. Soalnya mereka berdua mengconnect grup yang sama (grup 1 dan 2)


Sedangkan disini kita bisa ambil edge yang weight nya 3

**Lemma 4**
Untuk membuat suatu grup menjadi spesial, kita harus mengambil semua edge termurah yang menghubungkan grup tersebut dengan semua grup lainnya


Misalnya di gambar ini, untuk membuat grup 2 menjadi spesial, maka kita harus mengambil rute pesawat yang cost nya 5 dan 3.

Sehingga dari sini bisa kita simpulin :
Cost untuk membuat suatu grup menjadi spesial adalah weight terbesar dari semua edge edge yang dipilih (edge edge dengan weight minimal) yang menghubungkan grup ini dengan semua grup lainnya

Sehingga di gambar diatas, cost untuk membuat grup 2 menjadi spesial adalah 5

---

Dari lemma 1 sampai 4, seharusnya udah cukup sih buat mendapatkan full solution buat soal ini

---

### Full Solution

Untuk setiap grup, kita bisa cari tau cost untuk membuat grup itu menjadi spesial

Misalnya kita bisa lihat gambar di bawah ini

| Gambar | Keterangan |
| -------- | -------- |
|  | Cost untuk membuat grup 1 menjadi spesial adalah 6 |
|  | Cost untuk membuat grup 2 menjadi spesial adalah 5 |
|  | Cost untuk membuat grup 3 menjadi spesial adalah 6

Ingat objective di soal ini :
**Kita mau menentukan suatu nilai minimal K sehingga kita memiliki setidaknya X buah node yang spesial dengan nilai K tersebut**

Artinya, kita sekarang tinggal sort data yang kita dapat berdasarkan *cost minimal yang dibutuhkan setiap grup supaya menjadi spesial*

Kemudian setelah di sort, kita tinggal menghitung size dari setiap grup. Jadi kita proses satu per satu grup dari grup ke $1, 2, ..., G$. Dimana saat kita memproses grup ke $i$ artinya kita bisa memperoleh suatu nilai $X_i$ berdasarkan size dari grup ke $i$ ($size_i$) dengan cost sebesar $cost_i$

Misal kalo dari gambar diatas, maka kita bisa sort data menjadi :

| Grup | Cost untuk membuat spesial | Size dari grup |
| -------- | -------- | -------- |
| 2 | 5 | 5 |
| 1 | 6 | 3 |
| 3 | 6 | 4 |

Disini kita bisa menyimpulkan bahwa :

- Untuk mendapatkan setidaknya $5$ kota spesial kita membutuhkan cost senilai $5$
- Untuk mendapatkan setidaknya $8$ kota spesial kita membutuhkan cost senilai $6$
- Untuk mendapatkan setidaknya $12$ kota spesial kita membutuhkan cost senilai $6$

Jadi outputnya nanti
`5 5 5 5 5 6 6 6 6 6 6 6`

---
<center>
<h4>
END
</h4>
</center>