如何構建虛樹？
當我們獲得k個關鍵點后
首先把關鍵點按dfn（即原樹的dfs序）從小到大排序
然后開一個堆疊
堆疊的意義（性質）：從堆疊底到堆疊頂的元素構成（表示）虛樹中從上到下的一條鏈
虛樹構建程序：
依次列舉關鍵點x
-
當堆疊為慷訓堆疊中只有一個元素（即top<=1,top從0開始），直接把x壓入堆疊中（break/return）
-
否則令lca=LCA(x,stk[top])
-
如果lca=stk[top]
? 說明x應該接在stk[top]的下面（在虛樹中），所以直接把x壓入堆疊中（break/return）
-
如果lca!=stk[top]
? 說明x和stk[top]分屬lca的兩棵不同的子樹，而且stk[top]所在的子樹中已經構建完成了，所以我們把lca的stk[top]所在的那棵子樹彈堆疊，在彈堆疊的程序中建邊(單向邊)，直到 dfn[stk[top]]<=dfn[lca]<=dfn[stk[top-1]] (即lca在堆疊頂的兩元素的路徑上) 或 堆疊中元素小于2的時候停止彈堆疊，并判斷lca是否等于stk[top]
-
若不等，先從lca向stk[top]連邊，然后彈出堆疊頂，壓入lca，再壓入x
-
否則直接壓入x
-
-
列舉關鍵點結束后，若堆疊中的元素超過2個（即top>1），就不斷從stk[top-1]向stk[top]連邊，并彈出堆疊頂，
到此，虛樹構建完成，可以愉快地DP了，
總之，這個程序看似復雜，但只要想著要始終維護堆疊的性質（從堆疊底到堆疊頂的元素構成虛樹中從上到下的一條鏈）就不容易打錯了，寫的時候可以畫個圖，讓自己思路清晰
上馬：
void insert(int x){
if(top==1){stk[++top]=x;return;}
int lca=LCA(stk[top],x);
if(lca==stk[top]){stk[++top]=x;return;}
while(top>1&&dfn[stk[top-1]]>=dfn[lca]){
ADD(stk[top-1],stk[top]); // 單向
--top;
}
if(lca!=stk[top]){
ADD(lca,stk[top]);
stk[top]=lca;
}
stk[++top]=x;
}
int main(){
...
sort(x+1,x+k+1,cmp); //按dfn從小到大
top=0;ans=0;
stk[++top]=1;
for(int i=1;i<=k;++i){
if(x[i]==1)continue;
insert(x[i]);
}
while(top>1)ADD(stk[top-1],stk[top]),--top;
...
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/128442.html
標籤：其他
上一篇：資料結構篇——優先級佇列（堆）