我写的求lca代码犯了一个智障错误,但是依然有90分,其中#7RE。
我使用倍增求lca,具体的,我在让深度较大的点跳到较小深度的时候,判断条件写成了“深度大于另一个点的编号”,但是依然能过90分,是因为数据太水还是这样求出来的lca具有类似作用?
int getlca(int p1,int p2){
int pt=0;
if(dep[p1]<dep[p2]) swap(p1,p2);
while(dep[p1]>dep[p2]){
pt=0;
while(dep[fa[p1][pt+1]]>=p2) pt++;
p1=fa[p1][pt];
}
while(p1!=p2){
pt=0;
while(fa[p1][pt+1]!=fa[p2][pt+1]) pt++;
p1=fa[p1][pt],p2=fa[p2][pt];
}
return p1;
}