1552：点的距离（倍增求 lca）

const int lgN=20+5;
const int N=2e5+5;
 
    int n,m,t;
    int i,j,k;
    //int a[N];
    vector<int> G[N];
    int dep[N];
    int f[N][lgN];
    int lg[N];

void init()
{
    for(int i=1;i<=N;i++){
        lg[i]=lg[i-1];
        if(i==1<<lg[i-1]) lg[i]++;
    }
}  

void dfs(int u,int fa) //计算深度 dep ，以及个节点之间的关系 f[][]
{
    dep[u]=dep[fa]+1;
    f[u][0]=fa;

    for(int i=1;(1<<i)<=dep[u];i++){ //防止越界
        f[u][i]=f[f[u][i-1]][i-1];
    }
    int len=G[u].size();
    for(int i=0;i<len;i++){
        int v=G[u][i];
        if(v==fa) continue;
        dfs(v,u);
    }
} 

int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y); //x 向上跳
    while(dep[x]!=dep[y]) x=f[x][ lg[ dep[x]-dep[y] ] - 1 ];
    /*相当于
    for(int i=20;i>=0;i--){
        if(f[x][i]>=dep[y]){
            x=f[x][i];
        }
    }
    解释：
    lg[dep[x]-dep[y]] 是   log [ ( x 的深度- y 的深度)*2 ] 即 log(x 的深度 - y 的深度)+1
    我们想让 x 向上跳 dep[x]-dep[y] 层
    所以要减去 1
    */

    if(x==y) return x;

    for(int i=lg[ dep[x] ];i>=0;i--){ //防止越界
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}

int dis(int x,int y)
{
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}

int main()
{
    //IOS;
    init();
    while(~sd(n)){
        int x,y;
        for(i=1;i<n;i++){
            sdd(x,y);
            G[x].pb(y);
            G[y].pb(x);
        }
        dfs(1,0); //初始 根节点 1 的父节点是 0
        
        rush(){
            sdd(x,y);
            pd( dis(x,y) );
        }
    }
    //PAUSE;
    return 0;
}