标签：树，LCA
题目描述
三向城是一个巨大的城市，之所以叫这个名字，是因为城市中遍布着数不尽的三岔路口。（来自取名力为0的出题人）
具体来说，城中有无穷多个路口，每个路口有唯一的一个正整数标号。除了1号路口外，每个路口都连出正好3条道路通向另外3个路口：编号为x（x>1）的路口连出3条道路通向编号为x*2，x*2+1和x/2（向下取整）的3个路口。1号路口只连出两条道路，分别连向2号和3号路口。
所有道路都是可以双向通行的，并且长度都为1。现在，有n个问题：从路口x到路口y的最短路长度是多少？
输入格式
第一行包含一个整数n，表示询问数量；
接下来n行，每行包含两个正整数x, y，表示询问从路口x到路口y的最短路长度。
输出格式
输出n行，每行包含一个整数，表示对每次询问的回答。如果对于某个询问不存在从x到y的路径，则输出-1。
样例输入
3
5 7
2 4
1 1
样例输出
4
1
0
样例解释
5号路口到7号路口的路径为：5->2->1->3->7，长度为4；
2号路口到4号路口的路径为：2->4，长度为1；
1号路口到本身的路径长度为0；
数据范围
对30%的数据，x,y≤20；
对60%的数据，x,y≤105，n≤10；
对100%的数据，x,y≤109，n≤104。
先吐槽下出题人yy题目的语言功底……
T1难度，用LCA思想直接做
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxx=31;
int n,depx,depy,ans=0;
ll x,y;
int Deep(ll x)
{
rep(k,1,maxx)
if((ll)(1<<k)>x)return k;
}
int main()
{
freopen("city.in","r",stdin);
freopen("city.out","w",stdout);
n=read();
rep(i,1,n){
ans=0;
x=read(),y=read();
depx=Deep(x),depy=Deep(y);
if(depx<depy){swap(x,y);swap(depx,depy);}
dep(j,depx,depy+1){x/=2;ans++;}//cout<<ans<<"R\n";cout<<x<<' '<<depx<<endl;cout<<y<<' '<<depy<<endl;
dep(j,depy,0){if(x==y)break;x/=2,y/=2;ans+=2;}
printf("%d\n",ans);
}
return 0;
}
