#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 40010,M=N*2;
int e[M],ne[M],h[N],idx;
int fa[N][15+1];
int depth[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int q[N];
int hh,tt;
int root;
void bfs(){
memset(depth, 0x3f, sizeof depth);
depth[0]=0;
depth[root]=1;
q[0]=root;
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];~i;i=ne[i]){
int v=e[i];
if(depth[v]>depth[t]+1){//作为是否加点依据
depth[v]=depth[t]+1;
fa[v][0]=t;
q[++tt]=v;
for(int j=1;j<=15;j++)//这里要正着推
fa[v][j]=fa[fa[v][j-1]][j-1];//出界了就是0 v跳2^(j-1)步到达的点再跳2^(j-1)步为v跳2^j步到达的点
}
}
}
}
int lca(int a,int b){
if(depth[b]>depth[a])swap(a,b);//若a比b高,那就让b存a的值,a存b的值(接下来以a比b矮做)
//深度大,高度小
for(int i=15;i>=0;i--)
if(depth[fa[a][i]]>=depth[b])
a=fa[a][i];
if(a==b)return b;//若32行的if不执行,那么b本就比a高,若执行了(即本来a比b高),但现在b就存的是a的值,不要紧
//接下来是两个点的最近公共祖先不是其中任意一个点
for(int i=15;i>=0;i--)
if(fa[a][i]!=fa[b][i])
// ① 若此时a和b都是u的叶节点,那么无论跳2的多少次方步,39行的if永远不执行
// ② 若此时a和b的父节点不是同一个,那么a和b从大到小跳直到①的情况
//不会出界,因为出界等式两边都是0,if不执行
//不会跳过最近公共祖先,因为一旦跳过a和b的最近公共祖先,跳之前if不等式一定不成立。
a=fa[a][i],b=fa[b][i];
return fa[a//或b也行
][0];
}
int main()
{
int n,t;
cin>>n;
memset(h, -1, sizeof h);
while (n -- ){
int a,b;
cin>>a>>b;
if(b==-1)root=a;
else add(a, b),add(b,a);
}
bfs();
cin>>t;
while(t--){
int a,b;
cin>>a>>b;
int p=lca(a,b);
if(p==a)cout<<"1\n";//这一行
else if(p==b)cout<<"2\n";//和这一行只是某个点正好是两个点的最近公共祖先情况
else cout<<"0\n";
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
第一次写题解,下面的算法1算法2啥的忘删了……