LCA问题
本帖最后由 柿子饼同学 于 2022-7-15 10:40 编辑真的求求了 , 真的不知道为什么过不了 , 求指出 , 给鱼币 , 帮忙看下代码吧
题目 : 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{:10_266:} {:10_266:} {:10_266:}
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int dp, dep;
vector<int> tree;
int n, m, s, x, y;
void dfs(int ch, int pa){
if(ch == s){
dep = 1;
for(int i = 0; i <= 20; i++){
dp = ch;
}
}
else{
dp = pa;
dep = dep] + 1;
for(int i = 1; i <= 20; i++){
dp = dp];
}
}
for(auto i : tree){
if(i != pa) dfs(i, ch);
}
}
int lca(int x, int y){
if(dep < dep) swap(x, y);
for(int i = 20; i >= 0; i--){
if(dep] >= dep) x = dp;
}
if(x == y) return x;
for(int i = 20; 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);
cin >> n >> m >> s;
for(int i = 1; i < n; i++){
cin >> x >> y;
tree.push_back(y);
tree.push_back(x);
}
dfs(s, 0);
while(m--){
cin >> x >> y;
cout << lca(x, y) << endl;
}
return 0;
} 看了代码，发现的问题是越界，注意 12, 19, 30, 34 行， dp 数组的第二维度没有第 20 个元素。不喜欢洛谷所以不会去洛谷验证，用另外的评测网站测试了一下，修改后即通过测试，您可以参考。多说一句，这真的属于非常基础的，不应该出现的错误，如果因为这种问题困扰很久实在是太可惜了。 dolly_yos2 发表于 2022-7-15 17:20
看了代码，发现的问题是越界，注意 12, 19, 30, 34 行， dp 数组的第二维度没有第 20 个元素。不喜欢洛谷所 ...
哦哦哦哦哦哦 , 感谢 , 今天用了 log2n 打表的方法过了
现在会了
(没注意数组的问题...) {:5_108:} {:10_256:}{:10_256:}{:10_256:} {:10_323:} {:7_146:} {:10_256:} {:10_256:} {:10_254:} {:10_257:} 白嫖
页:
[1]