警示后人!!(如果你10pts)
查看原帖
警示后人!!(如果你10pts)
540287
stupid_collie楼主2023/2/8 13:01

记住,在求lca那里要先计算最小值再将点上移!!! (一开始以为是用bfs处理的问题qwq纠结了一个晚上啊啊啊啊啊啊)

int lca(int x,int y){
  int minv = INT_MAX;
  if(find(x)!=find(y))return -1;

  if(dep[x]>dep[y])std::swap(x,y);
  for(int i = l;i>=0;i--)
    if(dep[f[y][i]]>=dep[x])/*printf("%d %d %d\n",y,i,minlen[y][i]),*/minv = min(minv,minlen[y][i]),y = f[y][i];
  if(x==y)return minv;
  else{
    for(int i = l;i>=0;i--)
      if(f[x][i]!=f[y][i])minv = min(minv,min(minlen[x][i],minlen[y][i])),x = f[x][i],y = f[y][i];
  }

  return min(minv,min(minlen[x][0],minlen[y][0]));
}

2023/2/8 13:01
加载中...