題目描述 如題，給定一棵有根多叉樹，請求出指定兩個點直接最近的公共祖先。 輸入輸出格式 輸入格式： 第一行包含三個正整數N、M、S，分別表示樹的結點個數、詢問的個數和樹根結點的序號。 接下來N-1行每行包含兩個正整數x、y，表示x結點和y結點之間有一條直接連接的邊（數據保證可以構成樹）。 接下來M行 ...
題目描述
如題，給定一棵有根多叉樹，請求出指定兩個點直接最近的公共祖先。
輸入輸出格式
輸入格式：第一行包含三個正整數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。
很多人說這道題不能用倍增寫
其實是可以的，只不過需要加一點讀入優化罷了
註意倍增的最大值一定要取19而不能取20，因為這題卡常！！
代碼比較簡單，沒有用位運算，也寫了大量的註釋並標明瞭易錯點，大家可以參考一下
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=1000001; 7 int n,m,root; 8 struct node 9 { 10 int u; 11 int v; 12 int next; 13 }edge[MAXN]; 14 int num=1; 15 int head[MAXN]; 16 int deep[MAXN]; 17 int f[MAXN][20]; 18 void edge_add(int x,int y) 19 { 20 edge[num].u=x; 21 edge[num].v=y; 22 edge[num].next=head[x]; 23 head[x]=num++; 24 } 25 void build_tree(int p) 26 { 27 for(int i=head[p];i!=-1;i=edge[i].next)// 遍歷與p節點相鄰的節點 28 { 29 int will=edge[i].v; 30 if(deep[will]==0)// 如果點will沒有被訪問過的話 31 { 32 deep[will]=deep[p]+1;// 則點will的深度==p的深度+1 33 f[will][0]=p;// will點向上跳2^0的節點是p 34 build_tree(will);//繼續初始化will節點 35 } 36 } 37 } 38 void initialize_step() 39 { 40 for(int i=1;i<=19;i++) 41 for(int j=1;j<=n;j++) 42 f[j][i]=f[f[j][i-1]][i-1]; 43 // 第j個節點，向上跳i能到達的節點就是 跳到i-1處再向上跳i-1能到達的節點 44 // 因為倍增是以次方的形式增加的 45 } 46 int LCA(int x,int y) 47 { 48 if(deep[x]<deep[y])swap(x,y);// 如果說節點x的深度比節點y的深度小的話，就交換他倆的位置，讓x<y 49 for(int i=19;i>=0;i--)// 因為跳的步數越小越好，所以從最大的值開始跳 50 { 51 if(deep[f[x][i]]>=deep[y])// 如果跳完i步之後x還在y下方的話 ，這裡必須加等於號 52 x=f[x][i];// 就更新x的值，繼續跳 53 } 54 if(x==y)return y;//判斷一下，如果x和y在同一條線上，就直接返回x的值 ，y也可以 55 56 for(int i=19;i>=0;i--)//再讓x和y一起向上跳 57 if(f[x][i]!=f[y][i]) 58 x=f[x][i],y=f[y][i];// 如果他們跳完之後的祖先不相等的話,就繼續跳 59 return f[x][0];//按這樣跳下去，一定會跳到只要再跳一步就能找到最近公共祖先的位置！ 60 } 61 void read(int & x) 62 { 63 char c=getchar();x=0; 64 while(c<'0'||c>'9')c=getchar(); 65 while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();// 讀入優化，必須要有！ 66 } 67 int main() 68 { 69 //scanf("%d%d%d",&n,&m,&root); 70 read(n);read(m);read(root); 71 for(int i=1;i<=n;i++)head[i]=-1; 72 for(int i=1;i<=n-1;i++) 73 { 74 int x,y; 75 //scanf("%d%d",&x,&y); 76 read(x);read(y); 77 edge_add(x,y); 78 edge_add(y,x); 79 } 80 deep[root]=1;//將根節點的深度設為1 81 build_tree(root);// 建立起一棵樹 82 initialize_step();// 初始化向上跳的距離 83 for(int i=1;i<=m;i++) 84 { 85 int x,y; 86 //scanf("%d%d",&x,&y); 87 read(x);read(y);// 求x與y的最近公共祖先 88 printf("%d\n",LCA(x,y));// ans 89 } 90 return 0; 91 }
