这是一份普普通通的倍增LCA代码：

if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;--i)
  if(dep[fa[i][x]]>=dep[y]) x=fa[i][x];
if(x==y) return x;
for(int i=19;i>=0;--i)
  if(fa[i][x]!=fa[i][y]) 
    x=fa[i][x],y=fa[i][y];
return fa[0][x];

这样会 T 飞。但是改成下面的代码就能过：

if(dep[x]<dep[y]) swap(x,y);
int t=dep[x]-dep[y];
for(int i=19;i>=0;--i)
  if(t&(1<<i)) x=fa[i][x];
if(x==y) return x;
for(int i=19;i>=0;--i)
  if(fa[i][x]!=fa[i][y]) 
    x=fa[i][x],y=fa[i][y];
return fa[0][x];

二者的差距在于一个调用了过多的 dep 和 fa 数组，一个通过位运算枚举子集，前后时间差距 600ms。

请大家写 LCA 的时候选择更优秀的写法！！！