Gesaan dan konteks
Masalah pengekodan yang sukar ini menguji penguraian pokok, pra-pemprosesan jarak, dan pertanyaan dinamik. Pokok ini mempunyai n bucu dan n-1 tepi; operasi tiba secara dalam talian, keadaan awal mempunyai satu bucu hitam, dan togol adalah sewenang-wenangnya. Pertanyaan mesti mengembalikan jarak hitam terdekat semasa tanpa menelusuri semula keseluruhan pokok.
Perkara yang dinilai oleh penemu duga
- Bermula dengan garis dasar yang betul dan mengenal pasti penelusuran berulang sebagai hambatan (bottleneck).
- Membuktikan bahawa setiap nod mempunyai rantai leluhur-centroid dengan panjang logaritma dan mengekalkan jaraknya.
- Mengendalikan pengecualian komponen, jarak pendua, set hitam yang pada mulanya kosong, dan batas integer.
- Membandingkan centroid decomposition dengan BFS pelbagai sumber, heavy-light decomposition, dan varian sisipan sahaja.
Soalan penjelasan untuk ditanya
Sahkan bahawa pokok adalah statik, sama ada tepi mempunyai pemberat unit atau positif, sama ada operasi adalah secara dalam talian, sama ada pertanyaan juga memerlukan id nod, dan sama ada penyusunan semula dibenarkan. Pemberat tepi positif masih berfungsi dengan menyimpan jarak berpemberat; kemas kini tepi memerlukan reka bentuk pokok dinamik yang berbeza.
Rangka kerja jawapan 30 saat
Saya akan terlebih dahulu memberikan garis dasar: BFS dari u adalah linear bagi setiap pertanyaan. Kemudian saya membina centroid decomposition. Setiap nod menyimpan jaraknya ke setiap leluhur centroid, dan setiap centroid menyimpan jarak minimum dari nod yang sedang hitam. Pertanyaan meminimumkan "jarak dari u ke centroid ditambah jarak hitam terbaik centroid tersebut" di sepanjang leluhur centroid u; togol mengemas kini rantai yang sama. Rantai tersebut adalah logaritma, jadi operasi adalah logaritma selain kos timbunan (heap), dengan pra-pemprosesan linear-logaritma.
Jawapan mendalam langkah demi langkah
1. Wujudkan garis dasar dan hambatan
BFS dari u adalah betul, tetapi pertanyaan boleh melawat hampir setiap bucu. Selepas togol berulang kali, tiada ringkasan boleh guna semula mengenai bucu hitam mana yang dekat dengan u. BFS pelbagai sumber global hanya membantu apabila set hitam berubah secara kelompok, bukan dengan pembalikan dalam talian.
2. Pilih centroid dan bina rantai leluhur
Cari centroid bagi komponen bersambung semasa supaya penyingkirannya meninggalkan setiap komponen paling banyak separuh daripada saiz asal. Lakukan rekursi pada komponen tersebut untuk membentuk pokok centroid. Bucu asal u mempunyai rantai leluhur-centroid; pra-proses pasangan (centroid, distance) bagi setiap pautan. Saiz komponen berkurang separuh pada setiap peringkat, jadi panjang rantai adalah logaritma.
3. Kekalkan invarian kemas kini dan pertanyaan
Bagi setiap centroid c, kekalkan minimum dist(v,c) ke atas semua bucu v yang sedang hitam. Min-heap dengan pemadaman malas (lazy deletion) atau multiset menyokong ini. update(u) memasukkan atau membuang dist(u,c) di sepanjang rantai centroid u. query(u) meminimumkan dist(u,c) + best[c] pada rantai tersebut. Sebarang laluan dari u ke v yang hitam melalui centroid kongsi mereka pada beberapa peringkat penguraian, jadi satu calon mewakili laluan optimum; tiada cabang yang ditinggalkan.
4. Kendalikan jarak pendua dan pemadaman timbunan
Dengan dua heap, masukkan ke dalam heap aktif dan rekod pemadaman dalam heap mati; sebelum membaca elemen teratas, buang pasangan yang sama. Jarak yang sama memerlukan penyimpanan kedua-dua jarak dan id nod, jika tidak pemadaman satu nod boleh membuang nod yang lain. Gunakan satu kemas kini untuk nod hitam awal, dan kembalikan sentinel yang didokumenkan seperti -1 apabila set kosong.
5. Kekompleksan dan alternatif
Pra-pemprosesan merentasi setiap peringkat penguraian, memberikan masa O(n log n) dan O(n log n) pautan tersimpan. Setiap operasi mengimbas rantai logaritma dan melakukan operasi heap, menambah faktor heap logaritma. Jika nod hanya dimasukkan, satu heap adalah lebih mudah; jika operasi adalah agregat laluan bersekutu, heavy-light decomposition dengan segment tree adalah lebih langsung; operasi luar talian boleh menggunakan bahagi-dan-takluk masa.
6. Rangka pelaksanaan C++
Kod di bawah menggunakan tepi unit, menogol nod hitam, dan menjawab pertanyaan jarak terdekat. Kod pengeluaran boleh menggantikan penelusuran rekursif dengan timbunan (stack) eksplisit untuk pokok yang sangat dalam; bentuk rekursif memastikan invarian sentiasa kelihatan.
#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;}Jawapan model berkualiti tinggi
Saya akan mengubah pokok statik menjadi pokok centroid. Semasa pra-pemprosesan, setiap bucu merekodkan jaraknya ke setiap leluhur centroid; setiap centroid menyimpan jarak minimum dari bucu hitam semasa. Togol memasukkan atau membuang secara malas jarak di sepanjang rantai leluhur tersebut. Pertanyaan meminimumkan jarak ke setiap centroid ditambah jarak hitam terbaik centroid tersebut. Setiap laluan bertemu dengan centroid kongsiannya pada suatu peringkat, jadi bucu hitam optimum diwakili. Rantai centroid adalah logaritma, memberikan pra-pemprosesan O(n log n) dan operasi rantai logaritma, didarabkan dengan kos heap. Dengan sisipan sahaja saya akan membuang heap pemadaman; dengan tepi yang berubah-ubah saya akan memilih struktur pokok dinamik.
Kesilapan biasa
- BFS untuk setiap pertanyaan → betul tetapi terlalu perlahan secara dalam talian → nyatakan garis dasar, kemudian gunakan rantai centroid.
- Mengemas kini centroid terdekat sahaja → laluan boleh merentasi centroid yang lebih tinggi → simpan setiap leluhur centroid.
- Pemadaman malas berdasarkan jarak sahaja → nod jarak sama bertembung → sertakan id nod dalam kunci heap.
- Menganggap centroid decomposition sebagai LCA → ia menyelesaikan tugasan yang berbeza → nyatakan bahawa ini mengekalkan jarak dari nod ke set dinamik.
- Mengabaikan set hitam yang kosong → mengembalikan nilai besar yang tidak dimulakan → takrifkan dan jelaskan sentinel
-1.
Soalan susulan dan jawapan
Bagaimanakah pemberat tepi positif mengubah algoritma?
Kumpulkan pemberat tepi semasa mengumpul setiap rantai centroid dan simpan jarak berpemberat dalam heap. Penguraian masih menggunakan kiraan bucu komponen; invarian jarak minimum tidak berubah untuk pemberat bukan negatif.
Bagaimana jika pertanyaan mesti mengembalikan id nod hitam terdekat?
Simpan (distance, nodeId) dan bandingkan secara leksikografi. Ini memberikan id deterministik apabila terdapat persamaan jarak; pertanyaan membawa kedua-dua jarak dan id terbaik.
Mengapa tidak mengekalkan centroid induk u sahaja?
Nod hitam terdekat mungkin terletak dalam komponen anak yang berbeza, dengan laluan bertemu u pada centroid yang lebih tinggi. Memeriksa satu induk terlepas optimum rentas komponen, jadi rantai leluhur penuh diperlukan.
Bilakah heavy-light decomposition lebih baik?
Gunakan ia untuk agregat laluan bersekutu, pertanyaan laluan dua bucu sewenang-wenangnya, atau operasi set hitam yang bukan "jarak minimum dari satu bucu ke set dinamik". Centroid decomposition adalah paling kukuh apabila setiap pertanyaan berpaut pada satu bucu dan mengagregat ke atas set yang berubah.