当前位置: 首页> 财经> 股票 > 网站制作上网_高端女装有哪些品牌_搜索引擎营销的简称是_长沙关键词优化费用

网站制作上网_高端女装有哪些品牌_搜索引擎营销的简称是_长沙关键词优化费用

时间:2025/7/11 7:51:04来源:https://blog.csdn.net/LH_050902/article/details/147542251 浏览次数:0次
网站制作上网_高端女装有哪些品牌_搜索引擎营销的简称是_长沙关键词优化费用

预处理 O( n logn ),查询O( log n )

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=40010,M=2*N;//是无向边,边需要见两边int n,m;
vector<int> g[N];
//2的幂次范围 0~15
int depth[N],fa[N][15];
void bfs(int root){memset(depth,0x3f,sizeof depth);depth[0]=0,depth[root]=1;queue<int> q;q.push(root);while(q.size()){int t=q.front();q.pop();for(auto x:g[t]){if(depth[x]>depth[t]+1){depth[x]=depth[t]+1;q.push(x);fa[x][0]=t;for(int k=1;k<=15;++k){fa[x][k]=fa[fa[x][k-1]][k-1];}}}}
}
int lca(int a,int b){if(depth[a]<depth[b]) swap(a,b);for(int k=15;k>=0;--k){if(depth[fa[a][k]]>=depth[b]){a=fa[a][k];}}if(a==b) return a;for(int k=15;k>=0;--k){if(fa[a][k]!=fa[b][k]){a=fa[a][k];b=fa[b][k];}}return fa[a][0];
}
int main(){scanf("%d",&n);int root=0;for(int i=0;i<n;++i){int a,b;cin>>a>>b;if(b==-1) root=a;g[a].push_back(b),g[b].push_back(a);}bfs(root);scanf("%d",&m);while(m--){int a,b;cin>>a>>b;int p=lca(a,b);if(p==a) puts("1");else if(p==b) puts("2");else puts("0");}
}
/*
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
1
233 12
0
233 13
0
233 15
0
233 19
2
*/

关键字:网站制作上网_高端女装有哪些品牌_搜索引擎营销的简称是_长沙关键词优化费用

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: