LCA / Nowcoder 5086 C

發表於 更新於 分類於 Disqus： 文章字數： 118 所需閱讀時間 ≈ 1 分鐘

水题

调一万年，第一次就差三个地方

  1. 忘记了for work()

  2. assert()里面忘记双等号，写了个单个等号…

  3. LCA 写错了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int r(int i,int j){
  if(d[i] > d[j])swap(i,j);
  per(off,0,20){
    if(d[j]-d[i] >= (1<<off) ){
      j=f[j][off];
    }
  }
  if(i == j)return i;
  per(off,0,20){ // <---------------------------- 写成 per(off,1,20) 了
    if(f[i][off] != f[j][off]){
      i=f[i][off];
      j=f[j][off];
    }
  }
  return f[i][0];
}

不过

感觉LCA写得比原来熟很多了