最小公共祖先(_LCA_)問題

1、最小公共祖先( LCA )問題 poj1330,1986,1470-fuyuchang(cc)&internet 大綱n定義n將 LCA 問題轉(zhuǎn)化為 RMQ 問題nRMQ 的一般解法n1 RMQ 問題的快速解法nRMQ 的快速解法LCA 最小公共祖先在樹T中，結(jié)點u和v的最小公共祖先是它們共有的、離根結(jié)點最遠(yuǎn)的那個祖先結(jié)點。LCAT(u,v)uvRMQ 區(qū)間最小詢問詢問 RMQA(i,j) 返回的是數(shù)組Ai.j中最小元素的下標(biāo)。RMQA(i,j) 0163413 7191012 1 2RMQA(3,7) = 4A0A2A1A9A3 A4 A5 A6 A7A8時間復(fù)雜度標(biāo)記)n(g),n

2、(f預(yù)預(yù)處理時間處理時間單個詢問處理時單個詢問處理時間間LCA 一般的算法n對任意一對結(jié)點，分別找出它們到樹根的路徑，然后在這兩條路經(jīng)中找第一個公共的結(jié)點。 復(fù)雜度 = ) 1 (O),n(O3LCA普通算法的圖將 LCA 轉(zhuǎn)化為 RMQn如果有一個復(fù)雜度為 的 RMQ解法，那么就存在一個復(fù)雜度為 的LCA解法。 n變形 根據(jù)樹T構(gòu)造3個數(shù)組1. E1.2n-1：存放從樹根開始的Euler遍歷所經(jīng)過的結(jié)點編號。2. L1.2n-1：Li存放Ei結(jié)點在樹T中的深度。3. P1.n： Ri表示結(jié)點i在數(shù)組E中第一次出現(xiàn)的下標(biāo)。)(),(ngnf) 1 () 12(),() 12(OngnOnf8例

3、012369547下標(biāo) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18Eu: 0 1 2 1 3 1 0 4 0 5 6 5 7 8 7 5 9 5 0id: 0 1 2 1 2 1 0 1 0 1 2 1 2 3 2 1 2 1 0P: 0 1 2 4 7 9 10 12 13 16計算 LCAT(u,v)nEuler 遍歷過程中，夾在u和v第一次被訪問中間的結(jié)點是ERu,Rv。n其中深度最小的結(jié)點的下標(biāo)是 RMQL(Ru,Rv)。nLCAT(u,v)的結(jié)果就是 ERMQL(Ru,Rv)。例 LCAT(6,9)0123695847E: 0 1 2

4、 1 3 1 0 4 0 5 6 5 7 8 7 5 9 5 0L: 0 1 2 1 2 1 0 1 0 1 2 1 2 3 2 1 2 1 0P: 0 1 2 4 7 9 10 12 13 16R6R9E10,16RMQL(10,16) = 11LCAT(6,9) = E11=5復(fù)雜度分析預(yù)處理預(yù)處理n數(shù)組構(gòu)造：O(n)。n根據(jù)假設(shè)，對數(shù)組 L 進(jìn)行預(yù)處理：f(2n-1)。詢問處理詢問處理n三個數(shù)組的訪問： O(1)。n根據(jù)假設(shè)，對數(shù)組 L 進(jìn)行RMQ詢問處理：g(2n-1)。總共：總共： ) 1 () 12(),() 12(OngnOnfRMQ-LCA在線算法部分代碼nbool visit

5、MAXNODE;nint oula2*MAXNODE,distMAXNODE,posMAXNODE,minrmq182*MAXNODE,idMAXNODE;nint n,m;nvoid add(int u, int v, int w)nn edgee.to = v;n edgee.w = w;n edgee.next = headu;n headu = e+;nnvoid init()n rst(head,-1);n rst(visit,false);n tmpdfn=0;n index=0;n e=0;nnvoid dfs(int u)n visitu=true;n int len;n in

6、t oulanum=+tmpdfn;n oula+index=oulanum;n posu=index;n idoulanum=u;n for(int i=headu;i!=-1;i=edgei.next)n int next=edgei.to;n if(!visitnext)n /visitnext=true; dfs(next);n oula+index=oulanum;n n n return ;nRMQ-LCA在線算法部分代碼nint getmin(int l, int r)nint limit=(int)(log(r-l+1)*1.0)/log(2.0);n return min(m

7、inrmqlimitl,minrmqlimitr-(1limit)+1);nnvoid RMQ(int len,int *oularmq)n int limit,j;n limit=(int)(log(len*1.0) / log(2.0);n forle(i,1,len)minrmq0i=oularmqi;n forle(i,1,limit)n for(j=1;(j+(1i)-1=len;j+)n minrmqij=min(minrmqi-1j,minrmqi-1j+(1posr)cc=l,l=r,r=cc;n int ans=getmin(posl,posr);n return idans

8、;nTarjan-LCA離線算法n 核心思想：對于最近公共祖先問題，核心思想：對于最近公共祖先問題，我們先來看這樣一個性質(zhì)，我們先來看這樣一個性質(zhì)，當(dāng)兩個節(jié)點當(dāng)兩個節(jié)點（u，v）的最近公共祖先是）的最近公共祖先是x時，那么我時，那么我們可以確定的說，當(dāng)進(jìn)行后序遍歷的時們可以確定的說，當(dāng)進(jìn)行后序遍歷的時候，必然先訪問完候，必然先訪問完x的所有子樹，然后才的所有子樹，然后才會返回到會返回到x所在的節(jié)點。所在的節(jié)點。這個性質(zhì)就是我這個性質(zhì)就是我們使用們使用Tarjan算法解決最近公共祖先問算法解決最近公共祖先問題的核心思想。題的核心思想。Tarjan-LCA離線算法n 大概流程：每搜索完一棵子樹，則

9、可確定子樹內(nèi)的LCA詢問都已經(jīng)解決。其他的LCA詢問的結(jié)果由于沒訪問到，在子樹之外，這時把子樹的集合和當(dāng)前的節(jié)點的集合合并，并將當(dāng)前節(jié)點設(shè)為這個集合的公共祖先。之后繼續(xù)搜索下一個子樹，直到當(dāng)前節(jié)點的所有子樹搜索完。這時把當(dāng)前節(jié)點也設(shè)為被訪問過，同時可以處理有關(guān)當(dāng)前節(jié)點的LCA詢問，如果有一個從當(dāng)前節(jié)點到節(jié)點V的詢問，且V已被檢查過，則由于進(jìn)行的是DFS，當(dāng)前節(jié)點與V的最近公共祖先一定還沒有被檢查，而這個最近公共祖先的包含V的子樹一定已經(jīng)搜索過了，那么這個最近公共祖先一定是V所在集合的祖先Tarjan-LCA離線算法部分代碼nvoid init()n rst(visit,0);n rst(deg

10、,0);n forle(i,1,n)fatheri=i;n forle(i,1,n)n edgei.clear();n n rst(quesion,0);n rst(cnt,0);nnint getfather(int k)n if(fatherk=k)return fatherk;n fatherk=getfather(fatherk);n return fatherk;nnforl(i,0,n)n scanf(%d:(%d),&x,&m);n while(m-)n scanf(%d,&y);n edgex.push_back(y);n degy+;n n nvoid

11、 LCA(int u)n fatheru=u;n int k;n int len;n for(k=0,len=edgeu.size();klen;k+)n int yy=edgeuk;n LCA(yy);n fatheryy=u;n n visitu=true;n for(int i=1;i=n;i+)n if(visiti&quesionui)n int fa=getfather(i);n cntfa+=quesionui;n quesionui=quesioniu=0;n n n return;nRMQ 的一般解法n從現(xiàn)在開始，主要研究 RMQ 問題。n對每一對結(jié)點都預(yù)先求出 RM

12、Q 的解 -n改進(jìn)后使用一般的動態(tài)規(guī)劃 - ) 1 (),(3OnO) 1 (),(2OnORMQ 的稀疏表(Sparse Table)算法預(yù)處理預(yù)處理 n 計算矩陣n n時間：O(nlogn)。a1.anii+2j-1i+2j-1-1)lognj1 n,i(1 jMi,min) 12,(,12kAiiRMQjiMjikijA 1,2Mi Otherwise 1- jMi, 1,2AMi1- jAMi, ,1 - j1 - jjjjiMRMQ 的稀疏表(Sparse Table)算法RMQ(i,j)詢問處理詢問處理n n n時間：O(1)。n總復(fù)雜度： a1an.ij2k elements2k

13、 elements1ij2rmaxkrk, 12jM Otherwiseki,M k, 12jMAk, iMA) j , i (RMQkk) 1 (O),nlogn(O1 RMQ 分段 .B0B2n/lognBi.A .A0A2n/lognAiA：每一段的最小值B：此段最小值的下標(biāo)nlog21 n log2n 段，每段的大小是分成nA的大小 = 2n / logn。nST_預(yù)處理(A) nST(A)=1 RMQ 處理A)(log)loglog2(log2n log2nlogn log2n nOnnnn) 1 (O),n(O1 RMQ 詢問處理RMQ(i,j) 詢問處理詢問處理n需要計算以下這些

14、值：1. 從i到它所在段的末尾，這些數(shù)中間的最小值。2. 對A中夾在i和j分別所在的段之間的所有段的最小值。3. 從j所在段的起始到j(luò)，這些數(shù)中間的最小值。 .AiAj 1 2 31 RMQ 單段的一般處理單段的單段的ST 預(yù)處理預(yù)處理每一段所有段 .AiAj 1 2 3)nloglogn(logOn log21log n log21 )nloglogn(O觀察如果兩個數(shù)列X和Y有 CYiXi ,i 34 6 5 5 4 5 6 4 5A0A2A1A9A3 A4 A5 A6 A7 A8 0132 2 1 2 3 1 2A0A2A1A9A3 A4 A5 A6 A7A8+1-1-1-1+1+1-1

15、+1 +1),(),( , jiRMQjiRMQjiYX1 RMQ 單段的特殊處理n每段大小 = n每段的1序列長度 = n可能1序列的種數(shù) =n預(yù)處理所有的1序列 =n確定每一段所使用的1序列 = O(n)n總的時間復(fù)雜度 =nlog211log21nnn2121log21nnO2log) 1 (O),n(O一般 RMQ 問題n將 RMQ 轉(zhuǎn)化為 LCA斷言：n如果有一個復(fù)雜度為 的 LCA解法，那么就存在一個復(fù)雜度為 的RMQ解法。) 1 (O),n(O) 1 (O),n(O笛卡爾樹(Cartesian Tree)10163426 71910122522A0A2A1A9A3 A4 A5 A

16、6 A7A8n笛卡爾樹的樹根是數(shù)組中的最小元素。n每個結(jié)點記錄這個最小值元素的下標(biāo)。n這個元素將數(shù)組分成兩段，遞歸定義構(gòu)造笛卡爾樹。笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A84笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A846笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A8476笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A84769笛卡爾樹10163426 71910122522A0A2A1A9

17、A3 A4 A5 A6 A7A847698笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A8457698笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A84057698笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A84021357698線性時間構(gòu)造笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7 A8n設(shè)Ci是 A0,i的笛卡爾樹。n第 i+1 個結(jié)點一定屬于 Ci+1 最右側(cè)的那條路徑。n從 Ci 的最右側(cè)路徑

18、由下往上找，直到發(fā)現(xiàn)第 i+1 個結(jié)點可以放的位置。n由于每個結(jié)點只進(jìn)入和離開最右側(cè)路徑至多一次，所以這個算法的時間復(fù)雜度是O(n)的。線性時間構(gòu)造笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A8010線性時間構(gòu)造笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A8011025線性時間構(gòu)造笛卡爾樹10163426 71910122522A0A2A1A9A3 A4 A5 A6 A7A802110222534線性時間構(gòu)造笛卡爾樹101626 71910122522A0A2A1A9A3 A4 A5 A6 A7A80213 3 7343410222534線性時間構(gòu)造笛卡爾樹10163426 71910122