luogu P3379 【模板】最近公共祖先(LCA)
lca最近公共祖先,是指兩個點最近的祖先節點;求lca我知道的有三種倍增,
st表,tarjan,我要介紹的是倍增,我才不會告訴你我只會這一個。
話說我學lca可真的路途曲折,在qbxt,lcy dalao 的vector存圖讓我這個沒接觸過stl的蒟蒻完全懵圈,夏令營沒有講,學校里學長講我又完美錯過,心里的痛說不出,,,
還好又找學長單獨開了下小灶,額,跑偏了,回歸正題。
最近公共祖先的話,貌似挺有用,因為之前多次看到這個字眼(畢竟我只是剛剛打過模板的蒟蒻,題的話還沒有去接觸),其實我都快放棄lca了,但是學長突然留了一道題需要用lca,,,雖然我還是沒有打出來。。。有跑偏了
最近公共祖先,首先我們可以很容易想到,先從一個點往上找它的祖先節點,然后標記下,再找另外一個點的祖先節點,找到的第一個標記的點就是兩點的最近公共祖先,但當樹退化成鏈時,復雜度會變為O(N),這樣的話,顯然是不行的,所以我們在這個基礎上利用倍增的思想優化一下,一個一個的跳,有點慢,那我們就兩個兩個的跳,在此之前先將兩個點提到同一深度,然后用倍增的思想,同時往上跳2^n步,這樣的復雜度可以優化到O(logn)。
總結一下倍增求lca就以下幾點:
1.先確定兩個節點的高低,即先假設一個節點在下面,如果不是交換兩個節點,使假設的節點確實下面;
2.將兩點提至同一深度;
3.兩點同時往上跳,直至跳到最近公共祖先;
下面是luogu的模板題 附代碼+注釋
題目描述
如題,給定一棵有根多叉樹,請求出指定兩個點直接最近的公共祖先。
輸入輸出格式
輸入格式:
第一行包含三個正整數N、M、S,分別表示樹的結點個數、詢問的個數和樹根結點的序號。
接下來N-1行每行包含兩個正整數x、y,表示x結點和y結點之間有一條直接連接的邊(數據保證可以構成樹)。
接下來M行每行包含兩個正整數a、b,表示詢問a結點和b結點的最近公共祖先。
輸出格式:
輸出包含M行,每行包含一個正整數,依次為每一個詢問的結果。
輸入輸出樣例
輸入樣例#1:?復制
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
輸出樣例#1:?復制
4
4
1
4
4
說明
時空限制:1000ms,128M
數據規模:
對于30%的數據:N<=10,M<=10
對于70%的數據:N<=10000,M<=10000
對于100%的數據:N<=500000,M<=500000
樣例說明:
該樹結構如下:
第一次詢問:2、4的最近公共祖先,故為4。
第二次詢問:3、2的最近公共祖先,故為4。
第三次詢問:3、5的最近公共祖先,故為1。
第四次詢問:1、2的最近公共祖先,故為4。
第五次詢問:4、5的最近公共祖先,故為4。
故輸出依次為4、4、1、4、4。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cstdlib>using namespace std; int n; int m; int s; int x,y; int a,b; int p;const int maxn = 5211314; const int inf = 500521;int head[maxn]; int f[inf][20];//f[a][b]意思為a點往上面跳2^b步到達的祖先節點 int deep[maxn];//用來存點的深度 struct edge{//結構體存邊int from;int to;int next; }e[maxn]; inline int read(){//讀入優化int x = 0;int f = 1;char c = getchar();while(c<'0'||c>'9'){if(c=='-')f = -f;c = getchar();}while(c<='9'&&c>='0'){x = x*10+c-'0';c= getchar();}return x*f; }void add(int a,int b){//鄰接表存邊p++;e[p].from = head[a];e[p].to = b;head[a] = p; } void dfs(int root){//dfs深搜建樹for(int i = head[root]; i ; i = e[i].from){if(!deep[e[i].to]){deep[e[i].to] = deep[root] + 1;f[e[i].to][0] = root;dfs(e[i].to);}} } int lca(int x,int y){if(deep[x] < deep[y]){//確定兩點深度x^=y^=x^=y;//異或操作交換x,y兩點的值} //將兩點提至同一深度for(int i = 19; i>=0; i--){//這里的19根據數據范圍而定if(deep[f[x][i]]>=deep[y]){//這點很重要deep值越大說明深度值越大在下面,x = f[x][i];//我一開始想不明白的原因就是沒想通這里}}if(x == y)return x;//如果y是x的祖先節點或者x是y的祖先節點for(int i = 10; i>=0; i--){//讓兩點同時往上跳if(f[x][i] != f[y][i]){//如果相等說明已經是或者在最近公共祖先之上了x = f[x][i];//兩點不斷接近最近公共祖先y = f[y][i];//最終一定能到達最近公共祖先的兒子節點}}return f[x][0];//因為是兒子節點所以需要在往上跳一步 } int main(){n = read();m = read();s = read();for(int i = 1; i<=n-1; i++){x = read();y = read();add(x,y);add(y,x);}deep[s] = 1;f[s][0] = s;dfs(s);for(int i = 1; i<=19; i++){for(int j = 1; j<=n; j++){f[j][i] = f[f[j][i-1]][i-1];}}for(int i = 1; i<=m; i++){a = read();b = read();printf("%d\n",lca(a,b));}return 0; }轉載于:https://www.cnblogs.com/Euplectella/p/9907297.html
總結
以上是生活随笔為你收集整理的luogu P3379 【模板】最近公共祖先(LCA)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 军校提前批次志愿军校服从是什么意思?
- 下一篇: python之operator操作符函数