当前位置 博文首页 > Keven_11的博客:计蒜客lca批注
#include<bits/stdc++.h>
using namespace std;
const int NOIP=1e5+5;
int n,q,p[NOIP],eid;
void init(){
memset(p,-1,sizeof(p));//初始化
}
struct Edge{
int v,next;
}e[NOIP];
void insert(int u,int v){
e[eid].v=v;
e[eid].next=p[u];
p[u]=eid++;
}//链式前向星
/*
相当于我们用链表来模拟边的存储。
结构题edge的e来装一些分散的边。
eid是每加一条边都会增长的,表示当前边的下标。(从0开始)
p[u] 表示最后一个加入的u指向的边在 e 中的下标。最开始的值是-1。
在加边的时候:
void insert(int u,int v){
e[eid].v=v; //当前边指向的结点
e[eid].next=p[u]; //让当前边的next指向之前最后一个加入的u指向的边
p[u]=eid++; //更新p[u],更新完eid++
}
因此所有的边按照加入的顺序倒着形成一个链表,p[u]是头结点,
通过e[j].next可以访问下一个结点。直到 -1 表示这条链表已经走到了终点。
*/
int f[NOIP][20],d[NOIP];//f记录父节点,d记录深度
void dfs(int u){
d[u]=d[f[u][0]]+1;//从父节点的深度转移过来
for (int i=p[u];i!=-1;i=e[i].next){//链式前向星遍历树
int v=e[i].v;
if (v==f[u][0]){//不能遍历父节点,不然会无限循环下去
continue;
}
f[v][0]=u;//记录父节点
dfs(v);
}
}
int lca(int x,int y){//用倍增法,具体见计蒜客
if (d[x]<d[y]){
swap(x,y);//让x的深度比y的深度大(交换一下)
}
int k=0;
while ((1<<(k+1))<=d[x]){//相当于k=log2(d[x]);
k++;
}
for (int j=k;j>=0;j--){//让x和y深度一致
if(d[f[x][j]]>=d[y]){//如果x的父节点比y还深,
x=f[x][j];//那就向上跳一格,直到与y深度相同
}
}
if (x==y){//如果此时x就等于y,那就直接返回x或y
return x;//(return x; = return y;)
}
for (int j=k;j>=0;j--){
if (f[x][j]!=f[y][j]){
x=f[x][j];
y=f[y][j];
}
}
/*
从大到小枚举才会找到lca,即贪心的思路:让大的先加进去
if (f[x][j]!=f[y][j])是判断他俩目前找到的父节点是不是公共节点
,如果是,那可能是lca,也可能不是,这就不好说,
但是最后循环结束后因定能找到lca,这是个规律,所以
我们让他的某父节点不是公共的才跳
*/
return f[x][0];//循环结束后,x和y分别是它们 LCA 的儿子。
//因此它们的父节点就是 LCA
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
init();
cin>>n;
for (int i=1;i<n;i++){
int u,v;
cin>>u>>v;
insert(u,v);//插入
insert(v,u);//插入
}
dfs(1);//注意:节点编号有1,但无0。∴dfs(0)不对
for (int j=1;(1<<j)<=n;j++){
for (int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
//倍增法.i的2^j辈祖先等于i的2^(j-1)辈祖先
//的2^(j-1)辈祖先。
}
}
cin>>q;//询问次数
while (q--){
int x,y;
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
return 0;
}
?
cs