Submission #230711

---

Source Code Expand

#include <algorithm>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
using namespace std;
typedef pair<int ,int > P;
typedef long long ll;
int N;
vector<int> G[100005];
int d[100005];
int root;
int parent[20][100005];
int depth[100005];
void dfs(int v,int p,int d) {
    parent[0][v] = p;
    depth[v] = d;
    rep(i,G[v].size()) {
        if(G[v][i] != p) dfs(G[v][i],v,d+1);
    }
}
void init(int v) {
    for(int k=0;k+1<20;k++) {
        if(parent[k][v]<0) parent[k+1][v]=-1;
        else parent[k+1][v] = parent[k][parent[k][v]];

    }
}

int lca(int u,int v) {
    if(depth[u] > depth[v]) swap(u,v);

    rep(k,20) {
        if((depth[v]-depth[u])>>k &1) {
            v=parent[k][v];
        }
    }
    if(u==v) return u;
    for(int k=20-1;k>=0;k--) {
        if(parent[k][u]!=parent[k][v]) {
            u=parent[k][u];
            v=parent[k][v];
        }
    }

    return parent[0][u];
}

int main() {
    cin>>N;
    int maxi = 0;
    rep(i,N-1) {
        int x,y;
        cin>>x>>y;
        G[x].pb(y);
        G[y].pb(x);
        root = x;
        maxi=max(max(maxi,x),y);
    }
    root = maxi;
    dfs(root,-1,0);
    rep(i,maxi+1) init(i);
    int Q;
    cin>>Q;
    rep(i,Q) {
        int a,b;
        cin>>a>>b;
        int v=lca(a,b);
        int ans = depth[a]+depth[b]-depth[v]*2+1;
        //cout<<v<<endl;
        //cout<<depth[a]<<","<<depth[b]<<","<<depth[v]<<endl;
        cout<<ans<<endl;

    }
    return 0;
}

Submission Info

Judge Result