[已解决]LCA问题

柿子饼同学

真的求求了 , 真的不知道为什么过不了 , 求指出 , 给鱼币 , 帮忙看下代码吧
题目 : https://www.luogu.com.cn/problem/P3379
还有一组数据 :
输入 :

1. 10 10 8
   
2. 10 9
   
3. 3 1
   
4. 8 2
   
5. 3 8
   
6. 7 3
   
7. 5 9
   
8. 8 5
   
9. 8 6
   
10. 4 6
    
11. 8 4
    
12. 6 1
    
13. 7 1
    
14. 10 1
    
15. 6 1
    
16. 9 1
    
17. 4 1
    
18. 7 1
    
19. 10 1
    
20. 10 1
    

复制代码

输出 :

1. 8
   
2. 8
   
3. 3
   
4. 8
   
5. 8
   
6. 8
   
7. 8
   
8. 3
   
9. 8
   
10. 8

复制代码

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

复制代码

最佳答案

月排行榜 / 总排行榜

dolly_yos2

2022-7-15 17:20:04

看了代码，发现的问题是越界，注意 12, 19, 30, 34 行， dp 数组的第二维度没有第 20 个元素。不喜欢洛谷所以不会去洛谷验证，用另外的评测网站测试了一下，修改后即通过测试，您可以参考。多说一句，这真的属于非常基础的，不应该出现的错误，如果因为这种问题困扰很久实在是太可惜了。

跳转到最佳答案楼层

dolly_yos2

看了代码，发现的问题是越界，注意 12, 19, 30, 34 行， dp 数组的第二维度没有第 20 个元素。不喜欢洛谷所以不会去洛谷验证，用另外的评测网站测试了一下，修改后即通过测试，您可以参考。多说一句，这真的属于非常基础的，不应该出现的错误，如果因为这种问题困扰很久实在是太可惜了。

柿子饼同学

dolly_yos2 发表于 2022-7-15 17:20
看了代码，发现的问题是越界，注意 12, 19, 30, 34 行， dp 数组的第二维度没有第 20 个元素。不喜欢洛谷所 ...

哦哦哦哦哦哦 , 感谢 , 今天用了 log2n 打表的方法过了
现在会了
(没注意数组的问题...)

hornwong

kerln888

Passepartout

leletatann

1molHF

喝着红茶的红茶

kkl44stupid

uv阿布

鸢纸.

白嫖