[已解决]LCA问题

柿子饼同学

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

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

输出 :

8
8
3
8
8
8
8
3
8
8

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
int dp[N][20], dep[N];
vector<int> tree[N];
int n, m, s, x, y;

void dfs(int ch, int pa){
    if(ch == s){
        dep[ch] = 1;
        for(int i = 0; i <= 20; i++){
            dp[ch][i] = ch;
        }
    }
    else{
        dp[ch][0] = pa;
        dep[ch] = dep[dp[ch][0]] + 1;
        for(int i = 1; i <= 20; i++){
            dp[ch][i] = dp[dp[ch][i-1]][i-1];
        }
    }
    for(auto i : tree[ch]){
        if(i != pa) dfs(i, ch);
    }
}

int lca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 20; i >= 0; i--){
        if(dep[dp[x][i]] >= dep[y]) x = dp[x][i];
    }
    if(x == y) return x;
    for(int i = 20; i >= 0; i--){
        if(dp[x][i] != dp[y][i]){
            x = dp[x][i];
            y = dp[y][i];
        }
    }
    return dp[x][0];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> s;
    for(int i = 1; i < n; i++){
        cin >> x >> y;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }

    dfs(s, 0);

    while(m--){
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }

    return 0;
}

最佳答案

月排行榜 / 总排行榜

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阿布

鸢纸.

白嫖