Pertanyaan dan konteks
Masalah coding tingkat sulit ini menguji dekomposisi pohon, prapemrosesan jarak, dan kueri dinamis. Pohon memiliki n verteks dan n-1 sisi; operasi datang secara online, status awal memiliki satu verteks hitam, dan perubahan status bersifat bebas. Sebuah kueri harus mengembalikan jarak ke hitam terdekat saat ini tanpa menelusuri kembali seluruh pohon.
Apa yang dievaluasi pewawancara
- Memulai dengan baseline yang benar dan mengidentifikasi penelusuran berulang sebagai bottleneck.
- Membuktikan bahwa setiap simpul memiliki rantai leluhur-centroid dengan panjang logaritmik dan memelihara jarak-jaraknya.
- Menangani eksklusi komponen, jarak duplikat, himpunan simpul hitam yang awalnya kosong, dan batasan integer.
- Membandingkan centroid decomposition dengan multi-source BFS, heavy-light decomposition, dan varian yang hanya melakukan penyisipan (insertion-only).
Pertanyaan klarifikasi yang perlu diajukan
Pastikan bahwa pohon bersifat statis, apakah sisi-sisinya berbobot unit atau positif, apakah operasi bersifat online, apakah kueri juga membutuhkan id simpul, dan apakah penataan ulang urutan diperbolehkan. Bobot sisi positif tetap dapat bekerja dengan menyimpan jarak berbobot; pembaruan sisi memerlukan desain pohon dinamis yang berbeda.
Kerangka jawaban 30 detik
Pertama-tama saya akan memberikan baseline: BFS dari u membutuhkan waktu linier per kueri. Kemudian saya membangun centroid decomposition. Setiap simpul menyimpan jaraknya ke setiap leluhur centroid, dan setiap centroid menyimpan jarak minimum dari simpul yang saat ini berwarna hitam. Kueri meminimalkan "jarak dari u ke centroid ditambah jarak hitam terbaik centroid tersebut" di sepanjang leluhur centroid u; sebuah toggle memperbarui rantai yang sama. Rantai tersebut berukuran logaritmik, sehingga operasi bernilai logaritmik selain biaya heap, dengan prapemrosesan linier-logaritmik.
Jawaban mendalam langkah demi langkah
1. Menentukan baseline dan bottleneck
BFS dari u adalah benar, tetapi sebuah kueri dapat mengunjungi hampir setiap verteks. Setelah toggle berulang kali, tidak ada ringkasan yang dapat digunakan kembali mengenai verteks hitam mana yang dekat dengan u. BFS multi-source global hanya membantu ketika himpunan simpul hitam berubah secara batch, bukan dengan toggle online.
2. Memilih centroid dan membangun rantai leluhur
Temukan centroid dari komponen terhubung saat ini sedemikian rupa sehingga penghapusannya menyisakan setiap komponen dengan ukuran paling banyak setengah dari ukuran aslinya. Lakukan rekursi pada komponen-komponen tersebut untuk membentuk pohon centroid. Verteks asli u memiliki rantai leluhur-centroid; lakukan prapemrosesan pasangan (centroid, distance) untuk setiap penghubung. Ukuran komponen berkurang setengahnya di setiap tingkat, sehingga panjang rantai bersifat logaritmik.
3. Mempertahankan invarian pembaruan dan kueri
Untuk setiap centroid c, pertahankan nilai minimum dist(v,c) di semua verteks v yang saat ini berwarna hitam. Min-heap dengan lazy deletion atau multiset dapat mendukung ini. update(u) menyisipkan atau menghapus dist(u,c) di sepanjang rantai centroid u. query(u) meminimalkan dist(u,c) + best[c] pada rantai tersebut. Setiap jalur dari u ke v yang hitam melewati centroid bersama mereka pada suatu tingkat dekomposisi, sehingga satu kandidat mewakili jalur optimal; tidak ada cabang yang terlewatkan.
4. Menangani jarak duplikat dan penghapusan heap
Dengan dua heap, masukkan ke heap aktif dan catat penghapusan di heap tidak aktif; sebelum membaca elemen puncak, hapus pasangan yang sama. Jarak yang sama memerlukan penyimpanan jarak sekaligus id simpul, jika tidak, penghapusan satu simpul dapat menghapus simpul lain. Terapkan satu pembaruan untuk simpul hitam awal, dan kembalikan sentinel yang terdokumentasi seperti -1 ketika himpunan tersebut kosong.
5. Kompleksitas dan alternatif
Prapemrosesan menelusuri setiap tingkat dekomposisi, menghasilkan waktu O(n log n) dan O(n log n) penghubung yang disimpan. Setiap operasi memindai rantai logaritmik dan melakukan operasi heap, menambahkan faktor heap logaritmik. Jika simpul hanya disisipkan, satu heap akan lebih sederhana; jika operasinya adalah agregat jalur asosiatif, heavy-light decomposition dengan segment tree lebih langsung; operasi offline dapat menggunakan time divide-and-conquer.
6. Kerangka implementasi C++
Kode di bawah ini menggunakan sisi berbobot unit, mengubah status simpul hitam, dan menjawab kueri jarak terdekat. Kode produksi dapat menggantikan penelusuran rekursif dengan stack eksplisit untuk pohon yang sangat dalam; bentuk rekursif menjaga agar invarian tetap terlihat jelas.
#include <bits/stdc++.h>
using namespace std;
struct Entry { int d, u; bool operator>(const Entry& o) const { return tie(d,u) > tie(o.d,o.u); } };
int n; vector<vector<int>> g; vector<int> sub, dead, black;
vector<vector<pair<int,int>>> chain;
vector<priority_queue<Entry, vector<Entry>, greater<Entry>>> liveHeap, deadHeap;
void calcSize(int u,int p){sub[u]=1;for(int v:g[u])if(v!=p&&!dead[v]){calcSize(v,u);sub[u]+=sub[v];}}
int findCentroid(int u,int p,int total){for(int v:g[u])if(v!=p&&!dead[v]&&sub[v]>total/2)return findCentroid(v,u,total);return u;}
void collect(int u,int p,int c,int d){chain[u].push_back({c,d});for(int v:g[u])if(v!=p&&!dead[v])collect(v,u,c,d+1);}
void decompose(int entry){calcSize(entry,-1);int c=findCentroid(entry,-1,sub[entry]);dead[c]=1;collect(c,-1,c,0);for(int v:g[c])if(!dead[v])decompose(v);}
void clean(int c){while(!liveHeap[c].empty()&&!deadHeap[c].empty()&&liveHeap[c].top().d==deadHeap[c].top().d&&liveHeap[c].top().u==deadHeap[c].top().u){liveHeap[c].pop();deadHeap[c].pop();}}
void update(int u){black[u]^=1;for(auto [c,d]:chain[u]){if(black[u])liveHeap[c].push({d,u});else deadHeap[c].push({d,u});}}
int query(int u){const int INF=1e9;int ans=INF;for(auto [c,d]:chain[u]){clean(c);if(!liveHeap[c].empty())ans=min(ans,d+liveHeap[c].top().d);}return ans==INF?-1:ans;}Jawaban model berkualitas tinggi
Saya akan mengubah pohon statis menjadi pohon centroid. Selama prapemrosesan, setiap verteks mencatat jaraknya ke setiap leluhur centroid; setiap centroid menyimpan jarak minimum dari verteks hitam saat ini. Sebuah toggle menyisipkan atau menghapus secara lazy jarak di sepanjang rantai leluhur tersebut. Sebuah kueri meminimalkan jarak ke setiap centroid ditambah jarak hitam terbaik dari centroid tersebut. Setiap jalur bertemu dengan centroid bersamanya pada suatu tingkat, sehingga verteks hitam yang optimal selalu terwakili. Rantai centroid berukuran logaritmik, memberikan prapemrosesan O(n log n) dan operasi rantai logaritmik, dikalikan dengan biaya heap. Jika hanya ada penyisipan, saya akan menghapus heap penghapusan; jika sisi dapat berubah, saya akan memilih struktur pohon dinamis.
Kesalahan umum
- BFS untuk setiap kueri → benar tetapi terlalu lambat secara online → nyatakan baseline, lalu gunakan rantai centroid.
- Hanya memperbarui centroid terdekat → jalur dapat melintasi centroid yang lebih tinggi → simpan setiap leluhur centroid.
- Lazy deletion hanya berdasarkan jarak → simpul dengan jarak yang sama akan bertabrakan → sertakan id simpul di dalam kunci heap.
- Memperlakukan centroid decomposition sebagai LCA → keduanya menyelesaikan tugas yang berbeda → jelaskan bahwa metode ini memelihara jarak dari suatu simpul ke himpunan dinamis.
- Mengabaikan himpunan hitam yang kosong → mengembalikan nilai besar yang belum diinisialisasi → definisikan dan jelaskan sentinel
-1.
Pertanyaan lanjutan dan tanggapan
Bagaimana bobot sisi positif mengubah algoritma?
Akumulasikan bobot sisi saat mengumpulkan setiap rantai centroid dan simpan jarak berbobot di dalam heap. Dekomposisi tetap menggunakan jumlah verteks komponen; invarian jarak minimum tidak berubah untuk bobot non-negatif.
Bagaimana jika kueri harus mengembalikan id simpul hitam terdekat?
Simpan (distance, nodeId) dan bandingkan secara leksikografis. Ini memberikan id yang deterministik saat terjadi jarak yang sama; kueri membawa jarak dan id terbaik sekaligus.
Mengapa tidak hanya mempertahankan centroid induk dari u?
Simpul hitam terdekat mungkin berada di komponen anak yang berbeda, dengan jalur yang bertemu u pada centroid yang lebih tinggi. Hanya memeriksa satu induk akan melewatkan nilai optimal lintas-komponen, sehingga diperlukan rantai leluhur lengkap.
Kapan heavy-light decomposition lebih baik?
Gunakan itu untuk agregat jalur asosiatif, kueri jalur dua-verteks arbitrer, atau operasi himpunan hitam yang bukan berupa "jarak minimum dari satu verteks ke himpunan dinamis". Centroid decomposition paling unggul ketika setiap kueri terpaku pada satu verteks dan melakukan agregasi atas himpunan yang berubah-ubah.