Temu duga pengekodan: Bagaimanakah anda mengekalkan dynamic forest dengan link-cut tree?

Soalan dan skop

Anda mempunyai dynamic forest yang tepinya boleh ditambah atau dialih keluar dan bucunya memegang integer. Sokong link(u,v), cut(u,v), pertanyaan maksimum laluan, dan penambahan laluan. Terangkan perwakilan, access, makeroot, tag malas (lazy tags), ketepatan, dan kerumitan.

Struktur dynamic-tree oleh Sleator dan Tarjan menyambungkan dua pokok dan memotong satu tepi dengan operasi O(log n) terlunas. Isyarat temu duga yang dinilai ialah memisahkan laluan pokok yang diwakili daripada laluan pilihan (preferred paths) yang disimpan dalam auxiliary splay tree, bukannya sekadar menghafal templat.

Perkara yang diuji oleh penemu duga

Mengetahui bahawa link-cut tree mengekalkan represented forest dan auxiliary splay tree untuk laluan pilihan.
Melaksanakan isRoot, push, pull, putaran, dan splay dengan betul.
Menerangkan bagaimana access mengubah laluan ke represented root menjadi laluan pilihan.
Menggunakan tag pembalikan malas untuk laluan tanpa punca tanpa merosakkan susunan perambatan.
Mengesahkan ketersambungan sebelum link dan tepi yang tepat sebelum cut.
Menyatakan masa terlunas O(log n) dan membincangkan tatasusunan, kedalaman rekursi, serta ujian rawak.

Soalan untuk dijelaskan terlebih dahulu

Adakah struktur dijamin kekal sebagai forest, atau adakah operasi boleh mencipta kitaran? Link-cut tree tidak menyelesaikan ketersambungan graf dinamik umum.
Adakah kemas kini laluan berbentuk penambahan, peruntukan nilai (assignment), atau kedua-dua maksimum dan minimum? Setiap satu memerlukan algebra agregat dan lazy-tag yang berbeza.
Adakah nilai berada pada bucu atau tepi? Wakili tepi sebagai bucu maya apabila nilai tepi diperlukan.
Adakah ketahanan (persistence) atau kebersamaan (concurrency) diperlukan, atau adakah ini struktur dalam talian satu benang (single-threaded)?
Bolehkah input mengandungi pautan pendua, potongan yang tiada, atau gelung sendiri (self-loops)?

Jawapan 30 saat

Saya menggunakan satu auxiliary splay bagi setiap bucu yang diwakili. ch menyimpan anak-anak splay dan fa adalah sama ada auxiliary parent atau represented-path parent. access bergerak ke atas, menggantikan setiap anak kanan dengan laluan yang telah diproses; makeroot mengakses dan membalikkan pokok bantuan secara malas. link menyemak ketersambungan, melakukan makeroot pada satu titik hujung, dan menyambungkannya. cut melakukan makeroot pada satu titik hujung, mengakses titik hujung yang satu lagi, mengesahkan bahawa subpokok kiri adalah tepat titik hujung tepi tersebut, dan memutuskannya. Lakukan push sebelum putaran dan pull selepas kemas kini; operasi mempunyai kerumitan terlunas O(log n).

Perbincangan terperinci langkah demi langkah

1. Mewakili dua hubungan pokok

Anak-anak auxiliary splay menerangkan susunan pada laluan pilihan. Apabila nod ialah auxiliary root, fa bukan splay parent; ia adalah path parent dalam represented tree. Oleh itu isRoot(x) mesti menguji sama ada x bukan salah satu anak kepada fa[x], bukan sekadar sama ada fa[x] adalah sifar.

2. Mengekalkan agregat dan tag malas

Untuk maksimum laluan, pull(x) menggabungkan nilai pada x dengan kedua-dua subpokok bantuan. Penambahan laluan menggunakan tag add; pembalikan laluan menukar anak-anak di bawah tag rev. push mesti merambatkan pembalikan sebelum penambahan, atau sebaliknya mentakrifkan susunan gubahan yang terbukti.

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. Melaksanakan access

Tetapkan last = 0 dan bergerak dari x melalui fa: lakukan splay pada y, tetapkan anak kanan y kepada last, lakukan pull pada y, kemudian tetapkan last kepada y dan teruskan. Akhir sekali lakukan splay pada x asal. Laluan dari x ke represented root kini menjadi satu laluan pilihan yang susunan splay-nya boleh menjawab pertanyaan agregat laluan.

4. Melaksanakan makeroot

makeroot(x) memanggil access(x) dan mengenakan rev pada x. x menjadi punca represented-tree, membolehkan link(x,y) menyambungkan dua pokok mengikut arah yang dikehendaki. Jangan balikkan represented tree secara rekursif; auxiliary splay boleh memegang pembalikan malas tersebut.

5. Melaksanakan link dan cut

link(x,y) memanggil makeroot(x), menolak jika findroot(y) == x, kemudian menetapkan fa[x] = y. Untuk cut(x,y), panggil makeroot(x) dan access(y). Jika tepi wujud, anak kiri y ialah x dan x tidak mempunyai anak kanan; putuskan sambungan anak tersebut dan kosongkan induknya. Pemeriksaan struktur ini menghalang pemotongan tepi laluan yang salah.

6. Membuat pertanyaan dan mengemas kini laluan

split(x,y) ialah makeroot(x); access(y), meninggalkan auxiliary splay bagi y sebagai laluan x-ke-y. Baca mx[y] untuk nilai maksimum atau kenakan applyAdd pada y untuk kemas kini laluan. Tidak perlu memulihkan laluan pilihan; operasi access seterusnya akan menyusunnya semula.

7. Kerumitan dan ujian

Analisis Sleator–Tarjan memberikan masa terlunas O(log n) untuk link, cut, root, dan evert, dengan ruang O(n). Semak silang pelaksanaan kecil terhadap adjacency forest mudah: jana operasi link dan cut yang sah, bandingkan nilai maksimum dan penambahan laluan, serta sertakan pokok nod tunggal (singleton), makeroot berulang, access berturut-turut, cut tidak sah, nilai sama, dan nombor negatif.

Contoh jawapan berkualiti tinggi

Saya akan membiarkan fa membawa maksud sama ada auxiliary parent atau represented-path parent dan membezakannya dengan isRoot, daripada menganggap represented tree sebagai pokok binari biasa. Setiap nod splay menyimpan nilainya, maksimum subpokok, tag pembalikan, dan tag penambahan. access mendedahkan laluan pilihan; makeroot membalikkannya secara malas; split(x,y) menjadikan splay bagi y mewakili laluan x-ke-y.

link melakukan makeroot dan menolak titik hujung yang telah pun disambungkan. cut melakukan makeroot dan access, kemudian mengesahkan bahawa subpokok kiri y adalah tepat x sebelum memutuskannya. Lakukan push pada leluhur sebelum putaran dan pull selepas perubahan. Struktur ini menggunakan masa terlunas O(log n) dan ruang O(n); semakan silang rawak terhadap forest mudah meliputi pengesahan agregat, operasi tidak sah, dan kombinasi lazy-tag.

Kesilapan biasa

Menguji fa[x] == 0 untuk auxiliary root → path parent boleh bernilai bukan sifar → gunakan ujian isRoot berasaskan anak.
Mengabaikan operasi push pada leluhur sebelum putaran → pembalikan atau penambahan kekal tersembunyi → kumpulkan leluhur dan lakukan push mengikut urutan terbalik.
Melakukan cut tanpa menyemak tepi → tepi laluan yang salah dialih keluar → sahkan bentuk subpokok kiri selepas makeroot/access.
Melakukan link tanpa semakan ketersambungan → kitaran merosakkan varian forest → bandingkan punca terlebih dahulu.
Menganggap splay selepas access sebagai keseluruhan represented tree → hanya satu laluan pilihan didedahkan → bergantung pada operasi access masa hadapan.
Menguji pertanyaan tetapi tidak menguji kemas kini → pepijat lazy-tag kekal tersembunyi → bandingkan penambahan laluan rawak dengan forest mudah.

Soalan susulan dan jawapan

Bagaimanakah anda mengekalkan minimum laluan atau XOR?

Gantikan pull dengan agregat monoid yang diperlukan. XOR tidak sensitif terhadap susunan di bawah pembalikan; agregat bukan komutatif mesti mentakrifkan arah laluan dan susunan pembalikan secara eksplisit.

Bagaimanakah anda memasukkan wajaran tepi?

Pisahkan setiap tepi kepada bucu maya yang nilainya ialah wajaran tepi, kemudian gunakan pengagregatan bucu biasa. Uruskan bucu maya tersebut semasa melakukan link dan cut.

Mengapakah access boleh menggantikan subpokok kanan yang lama?

Subpokok lama kekal disambungkan melalui fa sebagai represented-path parent; ia cuma tidak lagi menjadi laluan pilihan. Hubungan auxiliary-child dan hubungan path-parent adalah berasingan.

Bolehkah peruntukan nilai laluan (path assignment) disokong?

Tambah tag assignment yang menulis ganti penambahan lama, mengemas kini nilai dan maksimum, serta bergabung dengan pembalikan dalam susunan yang ditetapkan. Algebra tag mestilah eksplisit dan boleh diuji.

Mengapakah findroot adalah betul?

Selepas access(x), tolak tag (push) sambil mengikuti anak paling kiri ke nod bantuan paling kiri. Nod tersebut ialah represented root; lakukan splay padanya untuk menstabilkan operasi seterusnya.

Bilakah anda patut mengelakkan link-cut tree?

Bagi forest statik, DFS/Euler tours atau heavy-light decomposition adalah lebih mudah. Bagi ketersambungan graf dinamik umum, concurrency, atau persistence, beban penyelenggaraan dan risiko pelaksanaan mungkin melebihi faedahnya.