Submission #1519485

---

Source Code Expand

#include <iostream>
#include <vector>
#define N 100000
#define L 17
using namespace std;
vector<int> g[N];
int d[N]={},p[L][N]={{}};
void f(int i){
    for(int j=0;j<g[i].size();j++){
        if(g[i][j]==p[0][i]) 
            continue;
        p[0][g[i][j]]=i;
        d[g[i][j]]=d[i]+1;
        f(g[i][j]);
    }
}           
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x-1].push_back(y-1);
        g[y-1].push_back(x-1);
    }
    f(0);
    for(int i=1;i<L;i++){
        for(int j=0;j<n;j++)
            p[i][j]=p[i-1][p[i-1][j]];
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a;
        cin>>b;
        a--;
        b--;
        int r=d[a]+d[b]+1;
        if(d[a]<d[b])
            swap(a,b);
        for(int i=0;i<L;i++){
            if((d[a]-d[b])&(1<<i))
                a=p[i][a];
        }
        for(int i=0;a!=b;i++){
            a=p[i][a];
            b=p[i][b];
        }
        cout<<r-d[a]*2<<endl;
    }
}

Submission Info

Judge Result