B - pog loves szh III
題目:添加連結描述
題意:找出區域l到r的LCA->找l和r的LCA
分析:
鍊式前向星存樹,先用dfs處理結點倍增關系。
然後從循環處理較深結點,直至兩節點位于同一層,即可共同向上找公共祖先:當兩節點父節點相遇時,一定為最小的公共祖先。
具體見代碼:
#include <iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=3e5+7;
int h[maxn],f[maxn][30],lg[maxn];
int head[maxn],nex[maxn<<1],to[maxn<<1],tot;
int n,m,s;
void add(int a,int b){//添加
to[++tot]=b;
nex[tot]=head[a];
head[a]=tot;
}//這輩子再也不用鍊式前向星
void dfs(int x,int fa){//dfs處理倍增
h[x]=h[fa]+1;f[x][0]=fa;//h表示層高
for(int i=1;(1<<i)<=h[x];i++)
f[x][i]=f[f[x][i-1]][i-1];//節點的2^i級祖先是結點的2^(i-1)級祖先的2^(i-1)級祖先
for(int i=head[x];i;i=nex[i]){
if(to[i]!=fa)dfs(to[i],x);
}
}
int LCA(int x,int y){
if(h[x]<h[y]) swap(x,y);//保證h[x]為大的那個
while(h[x]>h[y]) x=f[x][lg[h[x]-h[y]]-1];//使兩結點為同一層
if(x==y) return x;//相遇則為所求
for(int i=lg[h[x]]-1;i>=0;i--){
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
}//向上查詢直至父節點相遇
return f[x][0];//傳回其父節點
}
int main(){
int n;
while(cin>>n){
memset(head,-1,sizeof(head));
tot=0;
for(int i=0;i<n-1;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(1,0);
for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i);//初始化log值
int q;
cin>>q;
while(q--) {
int x,y;scanf("%d%d",&x,&y);
printf("%d\n",LCA(x,y));
}
}
}