大概模拟一下就好啦。
#include<bits/stdc++.h>
inline void read(int &a)
{
a=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
}
inline void write(int a)
{
if(a<0){putchar('-');a=-a;}
if(a>9)write(a/10);
putchar(a%10+'0');
}
int deep[31];
inline int lowerbound(int x)
{
int l=0,r=30;
while(l!=r)
{
int mid=l+r>>1;
if(deep[mid]>=x)r=mid;
else l=mid+1;
}
if(deep[l]==x)return l;
else return l-1;
}
inline int lca(int x,int y)
{
int k=0,deepx=lowerbound(x),deepy=lowerbound(y);
if(deepx<deepy){std::swap(x,y);std::swap(deepx,deepy);}
for(int i=1;i<=deepx-deepy;i++)x>>=1;
if(x==y)return deepx-deepy;
while(x!=y){k++;x>>=1;y>>=1;}
return (k<<1)+abs(deepy-deepx);
}
int main()
{
int a=1,n;
for(int i=0;i<=30;i++)
{
deep[i]=a;
a<<=1;
}
read(n);int x,y;
while(n--)
{
read(x);read(y);
write(lca(x,y));printf("\n");
}
return 0;
}