訪問網(wǎng)站人多的時候很慢是服務(wù)器問題還是帶寬pageadmin建站系統(tǒng)
LCA(Lowest Common Ancestor)
定義
在樹上取兩點?x,yx,y,他們的 LCA 為距離他們最近的公共祖先。
本章主要講的是倍增求 LCA。
暴力求取
- 從?xx?開始向上移動到根結(jié)點,并標記沿途結(jié)點。
- 從?yy?開始向上移動到根結(jié)點,第一個被標記的就是?xx?和?yy?的 LCA。
倍增求 LCA
從任意點對?(x,y)(x,y)?移到?xx?和?yy?的 LCA 的距離可拆分為?22?的冪的和。
若預(yù)處理任意點?xx?移動?22?的冪步所到達的結(jié)點編號,則不超過?\log_2{n}log2?n?次即可找到 LCA。
具體實現(xiàn)
first:預(yù)處理倍增 DP
定義狀態(tài)?dp_{i,j}dpi,j??表示點?ii?向上移動?2^j2j?步到達的結(jié)點編號。
狀態(tài)轉(zhuǎn)移方程:枚舉?jj?從?11?到?\log_2 nlog2?n,dp_{i,j}=dp_{dp_{i,j-1},j-1}dpi,j?=dpdpi,j?1?,j?1?。
初始狀態(tài):dp_{i,0}=fa_idpi,0?=fai?。
代碼片段
void pre_lca(int cur, int fa)
{dep[cur]=dep[fa]+1;dp[cur][0]=fa;for(int i=1;(1<<i)<=dep[cur];i++){dp[cur][i]=dp[dp[cur][i-1]][i-1];}for(int nxt:nbr[cur]){if(nxt!=fa)pre_lca(nxt,cur);}
}
second:處理單次詢問
第一步:約定深度較大的點,若?dep_x>dep_ydepx?>depy?,交換?xx?和?yy。
第二步:將深度較大的結(jié)點?yy?倍增向上跳至深度等于?xx。
第三步:判斷?xx?是否等于?yy。若已經(jīng)相等則?xx?為 LCA,停止尋找。
第四步:xx?和?yy?一起倍增向上跳,只要?xx?和?yy?不重合。
第五步:xx?向上一步即為 LCA。
代碼片段
int lca(int x, int y)
{if(dep[y]<dep[x])swap(x,y);for(int i=20;i>-1;i--){if(dep[dp[y][i]]>=dep[x]){y=dp[y][i];}}if(x==y)return x;for(int i=20;i>-1;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}return dp[x][0];
}
時間復(fù)雜度
預(yù)處理是?O(n \log_2 n)O(nlog2?n)?的,中間單次求取僅為?O(n)O(n)
模板代碼
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[500005][21],dep[500005], n, m, s;
vector<int> nbr[500005];
void pre_lca(int cur, int fa)
{dep[cur]=dep[fa]+1;dp[cur][0]=fa;for(int i=1;(1<<i)<=dep[cur];i++){dp[cur][i]=dp[dp[cur][i-1]][i-1];}for(int nxt:nbr[cur]){if(nxt!=fa)pre_lca(nxt,cur);}
}
int lca(int x, int y)
{if(dep[y]<dep[x])swap(x,y);for(int i=20;i>-1;i--){if(dep[dp[y][i]]>=dep[x]){y=dp[y][i];}}if(x==y)return x;for(int i=20;i>-1;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}return dp[x][0];
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m>>s;for(int i=1;i<n;i++){int x, y;cin>>x>>y;nbr[x].push_back(y);nbr[y].push_back(x);}pre_lca(s,0);for(int i=1;i<=m;i++){int x, y;cin>>x>>y;cout<<lca(x,y)<<"\n";}
}
LCA 應(yīng)用
- 求樹上兩點之間距離。
- 樹上差分。
LCA 求樹上兩點之間距離
維護?dis_xdisx??表示根結(jié)點到?xx?的距離。
xx?到?yy?的簡單路徑的長度為?dis_x+dis_y-2\times dis_{\texttt{lca}(x,y)}disx?+disy??2×dislca(x,y)?。
LCA 例題
first:P5836
方法 1
點權(quán)可以轉(zhuǎn)為?00?或?11,維護?dis_idisi??表示由根結(jié)點到?ii?的距離。
維護深度?dep_idepi?,對于每次詢問,若?(dis[a]+dis[b]-2*dis[lcad]+w[lcad]==dep[a]+dep[b]-2*dep[lcad]+1)&&c!='H'
?或?dis[a]+dis[b]-2*dis[lcad]+w[lcad]==0&&c=='H'
?則輸出?00,否則輸出?11。
方法 2
若一條邊的兩個端點的?ww?相同,則?unionn
?這兩個端點。
若一條路徑上點權(quán)相同,則兩個端點一定在同一集合。若該集合的權(quán)值不等于詢問,輸出?00,否則輸出?11。
while(m--)
{int x, y;char c;cin>>x>>y>>c;if(c=='H'){cout<<!(find(x)==find(y)&&w[x]==0);}else{cout<<!(find(x)==find(y)&&w[x]==1);}
}
方法 3
維護?dp_{i,j}dpi,j??表示?ii?向上動?2^j2j?步到達的結(jié)點編號,維護?yes_{i,j,0/1}yesi,j,0/1??表示?ii?向上跳?2^j2j?步是否有?ww?為?0/10/1?的點。
yes[cur][i][0]=yes[cur][i-1][0]|yes[dp[cur][i-1]][i-1][0],yes[cur][i][1]=yes[cur][i-1][1]|yes[dp[cur][i-1]][i-1][1];
。
初始狀態(tài):dp_{i,0}=fa_idpi,0?=fai?,yes_{i,0,w_{fa}}=1yesi,0,wfa??=1。
second:CF519E
若?AA?到?BB?的距離為奇數(shù),則答案直接為?00。
否則分情況討論:
-
中間位置的點?x=lcax=lca
xx?兒子結(jié)點中包含?AA?和?BB?的子樹剔除,其余為答案。
-
中間位置的點?xx?不是?lcalca
約定深度較大的點為?BB,找到?BB?向上距離?xx?一步的點?pp,則答案為?size_x-size_psizex??sizep?。
注意特殊情況:A==BA==B?時,答案為?nn。
從?lcalca?到?xx?的距離為?\frac{dep_B-dep_A}{2}2depB??depA??。
void work(int x,int y)
{if(x==y){cout<<n<<"\n";return ;}if(dep[x]==dep[y]){for(int i=14;i>=0;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}cout<<size[1]-size[x]-size[y]<<"\n";return ;}if(dep[x]<dep[y]) swap(x,y);if((dep[x]-dep[y])%2==1){cout<<"0\n";return ;}int x2=x,len=(dep[x]-dep[y])/2;for(int i=14;i>=0;i--){if(dep[dp[x][i]]>=dep[y]){x=dp[x][i];}}if(x==y){len+=dep[x];for(int i=14;i>=0;i--){if(dep[dp[x2][i]]>len){x2=dp[x2][i];}}cout<<size[dp[x2][0]]-size[x2]<<"\n";return ;}for(int i=14;i>=0;i--){if(dp[x][i]!=dp[y][i]){x=dp[x][i],y=dp[y][i];}}len+=dep[x]-1;for(int i=14;i>=0;i--){if(dep[dp[x2][i]]>len){x2=dp[x2][i];}}cout<<size[dp[x2][0]]-size[x2]<<"\n";
}
Third:P8972 一切都已過去
見?題解:P8972 『GROI-R1』 一切都已過去 - 洛谷專欄
方便閱讀搬過來。
從數(shù)據(jù)范圍很容易發(fā)現(xiàn),如果我們把邊權(quán)累乘再判整數(shù),炸掉是必然的,這時候,我們來發(fā)現(xiàn)一個性質(zhì):只有小數(shù)部分有?22?和?55?相乘的時候,才可能變成整數(shù)。當然,這并不是絕對的,例如?2.02 \times 52.02×5?就不是整數(shù)。從上面舉的例子很容易發(fā)現(xiàn)一個性質(zhì):兩個實數(shù)的乘積是否為整數(shù)與小數(shù)點數(shù)位也有關(guān)系。一對?22?和?55?可以抵消掉一個小數(shù)點數(shù)位(22?和?55?可以在任意且不同數(shù)位上,并且?22?和?55?的倍數(shù)也有用)。這時,我們可以將邊權(quán)通過不斷?\times 10×10?變成整數(shù),并分解質(zhì)因數(shù)分別求因數(shù)中?22?和?55?的個數(shù)(點權(quán)也要處理)。22?和?55?的個數(shù)求出來了,小數(shù)點數(shù)位也很好處理。最終的小數(shù)點位數(shù)應(yīng)該是所有路徑上的邊權(quán)小數(shù)點位數(shù)之和,所以我們在將邊權(quán)化整數(shù)時再維護一個變量統(tǒng)計小數(shù)點位數(shù)并記錄到鄰接矩陣里。若路徑?xx?到?yy?的總邊權(quán)乘上?xx?的點權(quán)得到的結(jié)果中?22?的個數(shù)和?55?的個數(shù)大于或等于總小數(shù)點位數(shù),則其為整數(shù)。分別維護即可。
注意:若邊權(quán)或點權(quán)為?00?則對應(yīng)維護的當前點權(quán)或點權(quán)的?22?和?55?賦予極大值。
Latex有雙倍問題,完整版請在安全訪問中心 - 洛谷查看