當(dāng)我們遇到一類頻繁詢問(wèn)關(guān)鍵點(diǎn)信息的題目時(shí),往往數(shù)據(jù)范圍頗大,而對(duì)關(guān)鍵點(diǎn)總和有一定限制,此時(shí)我們可以建立虛樹(shù),將問(wèn)題規(guī)模轉(zhuǎn)化為關(guān)鍵點(diǎn)總和級(jí)別的。
一、定義
什么是虛樹(shù)?
當(dāng)我們?cè)跇?shù)上有部分結(jié)點(diǎn)是無(wú)用的或用處不大的時(shí),我們可以將其在樹(shù)上刪去,僅僅保留關(guān)鍵點(diǎn)和連接關(guān)鍵點(diǎn)的邊。
如圖,圖中紅點(diǎn)是關(guān)鍵點(diǎn),右圖即為建立的虛樹(shù)。
二、性質(zhì)
1. 空間線性性質(zhì)
虛樹(shù)的點(diǎn)數(shù)是O(n)的,因?yàn)槠鋬H僅包含n個(gè)關(guān)鍵點(diǎn)和它們的lca,而lca的個(gè)數(shù)最多n?1個(gè),故虛樹(shù)結(jié)點(diǎn)數(shù)最多2n?1。
2. 結(jié)構(gòu)相似性質(zhì)
通過(guò)保留關(guān)鍵點(diǎn)的lca,我們可以盡可能地做到使虛樹(shù)結(jié)構(gòu)與原樹(shù)相似,這樣便使得我們的轉(zhuǎn)化是有效的。
三、建立過(guò)程
1. 初始化
初始化ST表并將關(guān)鍵點(diǎn)按照Dfs序排序。
2. 得到虛樹(shù)上的點(diǎn)
利用倍增求出排好序過(guò)后的關(guān)鍵點(diǎn)相鄰兩點(diǎn)的LCA,并加入關(guān)鍵點(diǎn)數(shù)組中,重新按照Dfs序排序并去重。
容易發(fā)現(xiàn),此時(shí)虛樹(shù)上的所有點(diǎn)都存在于數(shù)組中了。
3. 構(gòu)建虛樹(shù)
我們已經(jīng)得到了虛樹(shù)先序遍歷的結(jié)果,現(xiàn)在我們要構(gòu)建虛樹(shù),分為兩種情況討論。
(1)當(dāng)前點(diǎn)在棧頂子樹(shù)中
將棧頂和當(dāng)前點(diǎn)連邊,并將當(dāng)前點(diǎn)入棧。
(2)當(dāng)前點(diǎn)不在棧頂子樹(shù)中
說(shuō)明此時(shí)棧頂所在的一段鏈已經(jīng)Dfs完畢,彈棧,重復(fù)執(zhí)行該過(guò)程直到滿足情況
C語(yǔ)言網(wǎng)提供由在職研發(fā)工程師或ACM藍(lán)橋杯競(jìng)賽優(yōu)秀選手錄制的視頻教程,并配有習(xí)題和答疑,點(diǎn)擊了解:
一點(diǎn)編程也不會(huì)寫的:零基礎(chǔ)C語(yǔ)言學(xué)練課程
解決困擾你多年的C語(yǔ)言疑難雜癥特性的C語(yǔ)言進(jìn)階課程
從零到寫出一個(gè)爬蟲(chóng)的Python編程課程
只會(huì)語(yǔ)法寫不出代碼?手把手帶你寫100個(gè)編程真題的編程百練課程
信息學(xué)奧賽或C++選手的 必學(xué)C++課程
藍(lán)橋杯ACM、信息學(xué)奧賽的必學(xué)課程:算法競(jìng)賽課入門課程
手把手講解近五年真題的藍(lán)橋杯輔導(dǎo)課程