最近公共祖先

柿子饼同学

代码不知道问题出在哪 , 总是输出 0
求指出
题目:https://www.luogu.com.cn/problem/P3379

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 5e5 + 10;
   
5. //   ST表    深度数组 log2(n)存储
   
6. int dp[N][21], dep[N], lg[N];
   
7. int n, m, s;
   
8. vector<int> tree[N]; // 邻接表存储
   
9. 
   
10. void dfs(int x, int p){//x当前节点 , p是x的父母
    
11.     dep[x] = dep[p] + 1;
    
12.     dp[x][0] = p;
    
13.     for(int i = 1; (1<<i)<= dep[x]; i++){
    
14.         dp[x][i] = dp[dp[x][i-1]][i-1];
    
15.     }
    
16.     for(auto i : tree[x]){
    
17.         if(i != p) dfs(i, x);
    
18.     }
    
19. }
    
20. 
    
21. int lca(int x, int y){
    
22.     if(dep[x] < dep[y]) swap(x, y);
    
23.     for(int i = lg[dep[x]]; i >= 0; i--){
    
24.         if((1<<i)+dep[x] >= dep[y]){
    
25.             x = dp[x][i];
    
26.         }
    
27.     }
    
28.     if(x == y) return y;
    
29.     for(int i = lg[dep[x]]; i >= 0; i--){
    
30.         if(dp[x][i] != dp[y][i]){
    
31.             x = dp[x][i];
    
32.             y = dp[y][i];
    
33.         }
    
34.     }
    
35.     return dp[x][0];
    
36. }
    
37. 
    
38. int main(){
    
39.     ios::sync_with_stdio(0);
    
40.     cin.tie(0); cout.tie(0);
    
41.    
    
42.     int x, y;
    
43.     cin >> n >> m >> s;
    
44.     for(int i = 1; i <= n; i++){//预处理log2(n)
    
45.         lg[i] = lg[i-1] + ((1<<lg[i-1])==i);
    
46.     }
    
47.     for(int i = 1; i < n; i++){
    
48.         cin >> x >> y;
    
49.         tree[x].push_back(y);
    
50.         tree[y].push_back(x);
    
51.     }
    
52.     dfs(s, s);
    
53. 
    
54.     while(m--){
    
55.         cin >> x >> y;
    
56.         cout << lca(x, y) << endl;
    
57.     }
    
58. 
    
59.     return 0;
    
60. }

复制代码

谢谢大家了

jhq999

看看，没看明白
只能自己写一个还没通过

1. void huisu(int* a,int n,int pt1,int pt2)
   
2. {
   
3.     if(pt1==a[0]||pt2==a[0])printf("%d\n",a[0]);
   
4.     else
   
5.     {
   
6.         int i=0,j=0,pt3=pt1,pt4=pt2;
   
7.         while(pt3!=a[0])pt3=a[pt3],i++;//////计算到根节点的深度
   
8.         while(pt4!=a[0])pt4=a[pt4],j++;//////计算到根节点的深度
   
9.         pt3=pt1,pt4=pt2;
   
10.         while(1)////////跑到相同的深度
    
11.         {
    
12.             if(i==j)break;
    
13.             i>j?(pt3=a[pt3],i--):(pt4=a[pt4],j--);
    
14.         }
    
15.         while(pt3!=pt4)////////假如相同深度的值相同就是共同祖先
    
16.         {
    
17.             pt3=a[pt3],pt4=a[pt4];
    
18.         }
    
19.         printf("%d\n",pt3);
    
20.     }
    
21. 
    
22. }
    
23. int main()
    
24. {
    
25. 
    
26.     int n=0,m=0,s=0,i=0,id=0,parent=0;
    
27.     scanf("%d%d%d",&n,&m,&s);
    
28.     int* a=(int*)calloc(n+1,sizeof(int));
    
29.     int (*b)[2]=(int (*)[2])calloc(m*2,sizeof(int));
    
30.     a[0]=s;
    
31.     for(i=0;i<n-1;i++)
    
32.     {
    
33.         scanf("%d%d",&id,&parent);
    
34.         a[id]=parent;/////每个节点存储的是父节点下标
    
35.     }
    
36.     for(i=0;i<m;i++)
    
37.     {
    
38.         scanf("%d%d",b[i],b[i]+1);
    
39.     }
    
40.     for(i=0;i<m;i++)
    
41.     {
    
42. 
    
43.         huisu(a,n,b[i][0],b[i][1]);
    
44.     }
    
45.     free(b);
    
46.     free(a);
    
47. 
    
48.     return 0;
    
49. }
    

复制代码

柿子饼同学

jhq999 发表于 2022-7-14 18:14
看看，没看明白
只能自己写一个还没通过

唔 , 这个可能没有用 ST 表那么快