啟發(fā)式算法是什么呢?啟發(fā)式算法是基于人類的經(jīng)驗和直觀感覺,對一些算法的優(yōu)化。
最常見的就是并查集的按秩合并了,有帶按秩合并的并查集中,合并的代碼是這樣的:
void merge(int x, int y) { int xx = find(x), yy = find(y); if (size[xx] < size[yy]) swap(xx, yy); fa[yy] = xx; size[xx] += size[yy]; }
在這里,對于兩個大小不一樣的集合,我們將小的集合合并到大的集合中,而不是將大的集合合并到小的集合中。
讓高度小的樹成為高度較大的樹的子樹,這個優(yōu)化可以稱為啟發(fā)式合并算法。
樹上啟發(fā)式合并(dsu on tree)對于某些樹上離線問題可以速度大于等于大部分算法且更易于理解和實現(xiàn)的算法。
他是用來解決一類樹上詢問問題,一般這種問題有兩個特征:
(1)只有對子樹的詢問
(2)沒有修改
例題:給出一棵n個節(jié)點以1為根的樹,節(jié)點u的顏色為cu ,現(xiàn)在對于每個結點u詢問u子樹里一共出現(xiàn)了多少種不同的顏色。
對于這種問題解決方式大多是運用大量的數(shù)據(jù)結構(樹套樹等),如果可以離線,詢問的量巨大,是不是有更簡單的方法?
樹套樹可以解決,如果可以離線的話,樹上莫隊復雜度帶根號,現(xiàn)在我們要用一個帶log的算法。對于直接暴力復雜度為,即對每一個子節(jié)點進行一次遍歷,對于每個節(jié)點的答案是由其子樹和其本身得到的,現(xiàn)在考慮利用這個性質處理問題。
我們預處理出每個節(jié)點子樹的大小和其重兒子,重兒子同樹鏈剖分一樣,都是擁有節(jié)點最多子樹的兒子,這個過程O(n)求。
用cnt[i]表示顏色i出現(xiàn)的次數(shù),ans[u]表示節(jié)點u的答案。
遍歷一個節(jié)點u,我們按以下步驟遍歷:
(1)先遍歷u的輕(非重)兒子,并計算答案,但 不保留遍歷后它對 cnt 數(shù)組的影響;
(2)遍歷它的重兒子,保留它對 cnt 數(shù)組的影響;
(3)再次遍歷u的輕兒子的子樹結點,加入這些結點的貢獻,以得到u的答案。
上圖是一個例子。
這樣,對于一個節(jié)點,我們遍歷了一次重子樹,兩次非重子樹,顯然是最劃算的。
通過執(zhí)行這個過程,我們獲得了這個節(jié)點所有子樹的答案。
為什么不合并第一步和第三步呢,因為cnt數(shù)組不能重復使用,不然空間復雜度太高,需要O(n)內完成
若一個節(jié)點u被遍歷了x次,則其重兒子被遍歷x次,輕兒子(如果有的話)被遍歷2x次
這樣的復雜度是O(nlog n)
注意除了重兒子,每次遍歷完 cnt 要清零。
int sz[N],son[N]; void dfs1(int x){ /* 求解重兒子 */ sz[x] = 1; for(int i = head[x]; i; i = e[i].next){ int y = e[i].to; dfs1(y); sz[x] += sz[y]; if(sz[y] > sz[son[x]]) son[x] = y; } } void Delete(int x){ /* 刪除的內容 */ for(int i = head[x]; i; i = e[i].next) Delete(e[i].to); } void modify(int x,int fa){ /* 更新的內容 */ for(int i = head[x]; i; i = e[i].next) modify(e[i].to,fa); } void ins(int x){ /* 插入的內容 */ for(int i = head[x]; i; i = e[i].next) ins(e[i].to); } void dfs2(int x){ /* 求解輕兒子并清空 */ for(int i = head[x]; i; i = e[i].next) if(e[i].to != son[x]) dfs2(e[i].to), Delete(e[i].to); /* 求解重兒子并保留 */ if(son[x]) dfs2(son[x]); /* 用重兒子更新答案 */ /* 枚舉輕兒子更新答案,并加入輕兒子 */ for(int i = head[x]; i; i = e[i].next) if(e[i].to != son[x]) modify(e[i].to,x), ins(e[i].to); /* 用所有兒子更新答案 */ }
證明:
性質:一個節(jié)點到根的路徑上輕邊個數(shù)不會超過logn條
我們考慮一個點會被訪問幾次?
一個點被訪問只有兩種情況:
①在暴力統(tǒng)計輕邊的時候訪問到,次數(shù)<logn
②通過重邊/在遍歷的時候被訪問到,只有一次
如果統(tǒng)計一個點的貢獻的復雜度為O(1)的話,該算法的復雜度為O(nlogn)。
C語言網(wǎng)提供由在職研發(fā)工程師或ACM藍橋杯競賽優(yōu)秀選手錄制的視頻教程,并配有習題和答疑,點擊了解:
一點編程也不會寫的:零基礎C語言學練課程
解決困擾你多年的C語言疑難雜癥特性的C語言進階課程
從零到寫出一個爬蟲的Python編程課程
只會語法寫不出代碼?手把手帶你寫100個編程真題的編程百練課程
信息學奧賽或C++選手的 必學C++課程
藍橋杯ACM、信息學奧賽的必學課程:算法競賽課入門課程
手把手講解近五年真題的藍橋杯輔導課程