ST——LCA在线算法
安昙
2018-08-27 20:01:57
【LCA练习】最近公共祖先(版本1)
Description
给你一棵有根树，要求你计算出m对结点的最近公共祖先。
Input
输入文件的第一行包含两个整数n和m(2<=n,m<=200,000)，其中n为结点个数，结点编号为1到n；m表示询问次数。
接下来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的问题来解决
## 算法步骤：
1. 读入
1. 求出每一个节点的深度
1. 开一个数组p[i][k]表示，从i节点向上的2的k次方的祖先是哪一个节点
1. 初始化，动态规划求出p[i][k]
1. 在线解决每一对问题，把a节点和b节点调平，按照最大的k，递减向上回溯，直到a和b的上方一个节点就是共同祖先
## 伪代码：
```
#include<bits/stdc++.h>
using 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];
对每一对问题在线求解
}
```
------------
## 是时候用真正的代码压压惊了
```
#include<bits/stdc++.h>
using 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<<i)>=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;i<=n-1;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<=n;i++)
{
p[i][0]=prt[i];
}
for(int k=1;(1<<k)<=n;k++)
{
for(int i=1;i<=n;i++)
{
p[i][k]=p[p[i][k-1]][k-1];
}
}
for(int i=1;i<=m;i++)
{
int tis,tit;
scanf("%d%d",&tis,&tit);
printf("%d\n",deal(tis,tit));
}
}
```