Wawancara coding: Bagaimana Anda mengelola dynamic forest dengan link-cut tree?

Pertanyaan dan ruang lingkup

Anda memiliki dynamic forest yang sisi-sisinya (edges) dapat ditambah atau dihapus dan verteks-verteksnya menyimpan bilangan bulat. Dukung link(u,v), cut(u,v), kueri nilai maksimum jalur, dan penambahan nilai pada jalur. Jelaskan representasi, access, makeroot, lazy tag, kebenaran logika, dan kompleksitas.

Struktur dynamic-tree dari Sleator dan Tarjan menggabungkan dua pohon dan memotong suatu sisi dengan operasi O(log n) teramortisasi. Sinyal penting dalam wawancara adalah memisahkan jalur pohon yang direpresentasikan dari preferred path yang disimpan dalam auxiliary splay tree, bukan sekadar menghafal templat.

Hal yang diuji oleh pewawancara

Mengetahui bahwa link-cut tree mengelola represented forest dan auxiliary splay tree untuk preferred path.
Mengimplementasikan isRoot, push, pull, rotasi, dan splay dengan benar.
Menjelaskan bagaimana access mengubah jalur ke represented root menjadi sebuah preferred path.
Menggunakan tag pembalikan malas (lazy reversal tag) untuk jalur tanpa akar tetap tanpa merusak urutan propagasi.
Memvalidasi konektivitas sebelum link dan memverifikasi keberadaan sisi yang tepat sebelum cut.
Menyebutkan waktu teramortisasi O(log n) dan mendiskusikan array, kedalaman rekursi, serta pengujian acak (randomized testing).

Pertanyaan klarifikasi awal

Apakah struktur dijamin akan selalu berupa forest, atau apakah operasi dapat membentuk siklus? Link-cut tree tidak menyelesaikan konektivitas dynamic-graph umum.
Apakah pembaruan jalur berupa penambahan, penetapan nilai (assignment), atau mencakup nilai maksimum dan minimum? Masing-masing membutuhkan aljabar agregat dan lazy-tag yang berbeda.
Apakah nilai berada pada verteks atau sisi? Representasikan sisi sebagai verteks virtual jika nilai sisi diperlukan.
Apakah persistensi atau konkurensi diperlukan, atau apakah ini struktur online single-threaded?
Bisakah input memuat link duplikat, cut pada sisi yang tidak ada, atau self-loop?

Jawaban 30 detik

Saya menggunakan satu auxiliary splay per verteks yang direpresentasikan. ch menyimpan anak-anak splay dan fa berupa auxiliary parent atau represented-path parent. access berjalan ke atas, mengganti setiap anak kanan dengan jalur yang telah diproses sebelumnya; makeroot mengakses dan membalik auxiliary tree secara malas. link memeriksa konektivitas, melakukan makeroot pada salah satu titik ujung, lalu menghubungkannya. cut melakukan makeroot pada salah satu titik ujung, mengakses titik ujung lainnya, memverifikasi bahwa subtree kiri adalah persis titik ujung sisi tersebut, lalu memutuskannya. Lakukan push sebelum rotasi dan pull setelah pembaruan; operasinya memiliki kompleksitas teramortisasi O(log n).

Pembahasan mendalam langkah demi langkah

1. Merepresentasikan dua hubungan pohon

Anak-anak auxiliary splay mendeskripsikan urutan pada preferred path. Ketika sebuah node menjadi auxiliary root, fa bukan merupakan parent splay; melainkan path parent pada represented tree. Oleh karena itu, isRoot(x) harus menguji apakah x bukan anak dari fa[x], bukan hanya sekadar memeriksa apakah fa[x] bernilai nol.

2. Mengelola agregat dan lazy tag

Untuk nilai maksimum jalur, pull(x) menggabungkan nilai pada x dengan kedua auxiliary subtree. Penambahan jalur menggunakan tag add; pembalikan jalur menukar anak-anak di bawah tag rev. push harus mempropagasi pembalikan sebelum penambahan, atau mendefinisikan urutan komposisi yang terbukti benar.

text

pull(x): mx[x] = max(value[x], mx[ch[x][0]], mx[ch[x][1]])
applyAdd(x,d): value[x] += d; mx[x] += d; add[x] += d
applyRev(x): swap(ch[x][0], ch[x][1]); rev[x] ^= true

3. Mengimplementasikan access

Set last = 0 dan telusuri ke atas dari x melalui fa: lakukan splay pada y, set anak kanan y ke last, lakukan pull pada y, lalu set last ke y dan lanjutkan. Terakhir, lakukan splay pada x awal. Jalur dari x ke represented root sekarang menjadi satu preferred path yang urutan splay-nya dapat menjawab kueri agregat jalur.

4. Mengimplementasikan makeroot

makeroot(x) memanggil access(x) dan menerapkan rev pada x. x menjadi root pada represented-tree, sehingga link(x,y) dapat menggabungkan dua pohon ke arah yang diinginkan. Jangan membalik represented tree secara rekursif; auxiliary splay dapat menangani pembalikan malas ini.

5. Mengimplementasikan link dan cut

link(x,y) memanggil makeroot(x), menolak jika findroot(y) == x, kemudian mengatur fa[x] = y. Untuk cut(x,y), panggil makeroot(x) dan access(y). Jika sisi tersebut ada, anak kiri y adalah x dan x tidak memiliki anak kanan; putuskan anak tersebut dan bersihkan pointer parent-nya. Pemeriksaan struktural ini mencegah terputusnya sisi jalur yang salah.

6. Kueri dan pembaruan jalur

split(x,y) adalah makeroot(x); access(y), yang menjadikan auxiliary splay y mewakili jalur dari x ke y. Baca mx[y] untuk mendapatkan nilai maksimum atau terapkan applyAdd pada y untuk pembaruan jalur. Tidak perlu memulihkan preferred path sebelumnya; pemanggilan access berikutnya akan mengaturnya kembali.

7. Kompleksitas dan pengujian

Analisis Sleator–Tarjan menghasilkan kompleksitas waktu teramortisasi O(log n) untuk link, cut, root, dan evert, dengan ruang O(n). Lakukan uji silang (cross-check) implementasi kecil terhadap representasi adjacency forest sederhana: buat link dan cut yang valid, bandingkan nilai maksimum dan penambahan jalur, serta sertakan pohon simpul tunggal (singleton), makeroot berulang, access berturut-turut, cut tidak valid, nilai yang sama, dan nilai negatif.

Contoh jawaban berkualitas tinggi

Saya akan membiarkan fa merepresentasikan auxiliary parent atau represented-path parent dan membedakannya menggunakan isRoot, alih-alih memperlakukan represented tree sebagai pohon biner biasa. Setiap node splay menyimpan nilainya, nilai maksimum subtree, tag pembalikan, dan tag penambahan. access mengekspos preferred path; makeroot membaliknya secara malas; split(x,y) membuat splay y merepresentasikan jalur dari x ke y.

link melakukan makeroot dan menolak titik ujung yang sudah terhubung. cut melakukan makeroot dan access, lalu memverifikasi bahwa subtree kiri y adalah tepat x sebelum memutuskannya. Lakukan push pada leluhur sebelum rotasi dan pull setelah perubahan. Struktur ini menggunakan waktu teramortisasi O(log n) dan ruang O(n); uji silang acak terhadap forest sederhana mencakup pengujian agregat, operasi tidak valid, dan kombinasi lazy-tag.

Kesalahan umum

Memeriksa fa[x] == 0 untuk auxiliary root → path parent bisa bernilai bukan nol → gunakan pengujian isRoot berbasis anak.
Melewatkan operasi push leluhur sebelum rotasi → pembalikan atau penambahan tetap tersembunyi → kumpulkan leluhur dan lakukan push dengan urutan terbalik.
Melakukan cut tanpa memeriksa sisi → sisi jalur yang salah terhapus → verifikasi bentuk subtree kiri setelah makeroot/access.
Melakukan link tanpa pemeriksaan konektivitas → siklus akan merusak invarian forest → bandingkan root terlebih dahulu.
Menganggap splay setelah pemanggilan access sebagai seluruh represented tree → hanya satu preferred path yang diekspos → serahkan pengorganisasian pada operasi access berikutnya.
Hanya menguji kueri tanpa menguji pembaruan → bug pada lazy-tag tetap tersembunyi → bandingkan penambahan jalur acak dengan forest sederhana.

Pertanyaan lanjutan dan jawaban

Bagaimana Anda mengelola nilai minimum atau XOR pada jalur?

Ganti pull dengan agregat monoid yang diperlukan. XOR tidak sensitif terhadap urutan di bawah operasi pembalikan; agregat non-komutatif harus mendefinisikan arah jalur dan urutan pembalikan secara eksplisit.

Bagaimana Anda menangani bobot sisi?

Pecah setiap sisi menjadi verteks virtual yang nilainya merupakan bobot sisi tersebut, lalu gunakan agregasi verteks standar. Kelola verteks virtual tersebut saat melakukan link dan cut.

Mengapa access dapat menggantikan subtree kanan yang lama?

Subtree yang lama tetap terhubung melalui fa sebagai represented-path parent; subtree tersebut hanya tidak lagi menjadi preferred path. Hubungan auxiliary-child dan hubungan path-parent terpisah satu sama lain.

Bisakah pembaruan berupa assignment pada jalur didukung?

Tambahkan tag penugasan (assignment) yang menimpa penambahan lama, memperbarui nilai dan maksimum, serta berkomposisi dengan operasi pembalikan dalam urutan yang ditentukan. Aljabar tag harus eksplisit dan dapat diuji.

Mengapa findroot bekerja dengan benar?

Setelah access(x), lakukan push tag sambil menelusuri anak paling kiri menuju node auxiliary paling kiri. Node tersebut adalah represented root; lakukan splay padanya untuk menstabilkan operasi berikutnya.

Kapan sebaiknya Anda menghindari link-cut tree?

Untuk forest statis, DFS/Euler tour atau heavy-light decomposition jauh lebih sederhana. Untuk konektivitas graf dinamis umum, konkurensi, atau persistensi, beban pemeliharaan dan risiko implementasi mungkin melebihi manfaat yang diperoleh.