最近公共祖先
本帖最后由 柿子饼同学 于 2022-7-14 13:50 编辑代码不知道问题出在哪 , 总是输出 0
求指出
题目:https://www.luogu.com.cn/problem/P3379
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
// ST表 深度数组 log2(n)存储
int dp, dep, lg;
int n, m, s;
vector<int> tree; // 邻接表存储
void dfs(int x, int p){//x当前节点 , p是x的父母
dep = dep + 1;
dp = p;
for(int i = 1; (1<<i)<= dep; i++){
dp = dp];
}
for(auto i : tree){
if(i != p) dfs(i, x);
}
}
int lca(int x, int y){
if(dep < dep) swap(x, y);
for(int i = lg]; i >= 0; i--){
if((1<<i)+dep >= dep){
x = dp;
}
}
if(x == y) return y;
for(int i = lg]; i >= 0; i--){
if(dp != dp){
x = dp;
y = dp;
}
}
return dp;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int x, y;
cin >> n >> m >> s;
for(int i = 1; i <= n; i++){//预处理log2(n)
lg = lg + ((1<<lg)==i);
}
for(int i = 1; i < n; i++){
cin >> x >> y;
tree.push_back(y);
tree.push_back(x);
}
dfs(s, s);
while(m--){
cin >> x >> y;
cout << lca(x, y) << endl;
}
return 0;
}
谢谢大家了 本帖最后由 jhq999 于 2022-7-14 18:30 编辑
看看，没看明白
只能自己写一个还没通过{:5_104:}
void huisu(int* a,int n,int pt1,int pt2)
{
if(pt1==a||pt2==a)printf("%d\n",a);
else
{
int i=0,j=0,pt3=pt1,pt4=pt2;
while(pt3!=a)pt3=a,i++;//////计算到根节点的深度
while(pt4!=a)pt4=a,j++;//////计算到根节点的深度
pt3=pt1,pt4=pt2;
while(1)////////跑到相同的深度
{
if(i==j)break;
i>j?(pt3=a,i--):(pt4=a,j--);
}
while(pt3!=pt4)////////假如相同深度的值相同就是共同祖先
{
pt3=a,pt4=a;
}
printf("%d\n",pt3);
}
}
int main()
{
int n=0,m=0,s=0,i=0,id=0,parent=0;
scanf("%d%d%d",&n,&m,&s);
int* a=(int*)calloc(n+1,sizeof(int));
int (*b)=(int (*))calloc(m*2,sizeof(int));
a=s;
for(i=0;i<n-1;i++)
{
scanf("%d%d",&id,&parent);
a=parent;/////每个节点存储的是父节点下标
}
for(i=0;i<m;i++)
{
scanf("%d%d",b,b+1);
}
for(i=0;i<m;i++)
{
huisu(a,n,b,b);
}
free(b);
free(a);
return 0;
}
jhq999 发表于 2022-7-14 18:14
看看，没看明白
只能自己写一个还没通过
唔 , 这个可能没有用 ST 表那么快
页:
[1]