【LCA练习】最近公共祖先(版本1)
Description
给你一棵有根树，要求你计算出m对结点的最近公共祖先。
Input
输入文件的第一行包含两个整数n和m(2
接下来n-1行，每行两个整数x和y，表示结点x是结点y的父亲结点；
接下来的m行，每行两个整数a和b，要求计算出结点a和b的最近公共 祖先。
Output
输出文件共m行，分别为每对结点的最近公共祖先编号。
Sample Input
5 3
2 3
3 4
3 1
1 5
3 5
4 5
1 2
Sample Output 3
3
2
思想：
转化为类似于RMQ的问题来解决
算法步骤：
- 读入
- 求出每一个节点的深度
- 开一个数组p[i][k]表示，从i节点向上的2的k次方的祖先是哪一个节点
- 初始化，动态规划求出p[i][k]
- 在线解决每一对问题，把a节点和b节点调平，按照最大的k，递减向上回溯，直到a和b的上方一个节点就是共同祖先
伪代码：
#includeusing namespace std; struct 前向星 { }a[100000]; int h[300000]; int cnt; int n,m; int prt[300000]; int root; int d[300000]; int p[300000][20]; void Union(int x,int y) { 连接x,y节点 } void getdeep(int v0,deep) { 从根节点递归求出每一个节点的深度 } int deal(int x,int y)//在线ST算法 { 1.使d[x]>d[y],便于操作 2.求出最大的k（最大向上扩展高度2的k次方） 3.调平x,y节点 4.特判 5.以k的递减,x,y同时向上爬,如果。。。。。。 6.返回p[x][0]; } int main() { cin>>n>>m; 循环读入 找根节点 递归深度 *初始化 DP求出p[i][k]; 对每一对问题在线求解 }
是时候用真正的代码压压惊了
#includeusing namespace std; struct eg { int next,to; }a[300000]; int h[300000]; int cnt; int n,m; int prt[300000]; int root; int d[300000]; int p[300000][20]; void Union(int x,int y) { cnt++; a[cnt].to=y; a[cnt].next=h[x]; h[x]=cnt; } void getdeep(int v0,int deep) { d[v0]=deep; for(int i=h[v0];i;i=a[i].next) { getdeep(a[i].to,deep+1); } } int deal(int x,int y) { if(d[x]d[y])swap(x,y); int key=log(d[x])/log(2); for(int i=key;i>=0;i--) { if(d[x]-(1=d[y])x=p[x][i]; } if(x==y)return y; for(int i=key;i>=0;i--) { if(p[x][i]!=p[y][i])x=p[x][i],y=p[y][i]; } return p[x][0]; } int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i1;i++) { int tis,tit; scanf("%d%d",&tis,&tit); Union(tis,tit); prt[tit]=tis; } int root=1; while(prt[root])root=prt[root]; getdeep(root,1); for(int i=1;i) { p[i][0]=prt[i]; } for(int k=1;(1) { for(int i=1;i) { p[i][k]=p[p[i][k-1]][k-1]; } } for(int i=1;i) { int tis,tit; scanf("%d%d",&tis,&tit); printf("%d\n",deal(tis,tit)); } }