Submission #6900818

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}
const int V_MAX = 1e5+10;
int V;
vector<vector<int> > G(V_MAX);

template< typename G >
struct DoublingLowestCommonAncestor{
  const int LOG;
  vector<int> dep;
  const G &g;
  vector<vector<int> > table;

  DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
    table.assign(LOG, vector<int>(g.size(),-1));
  }

  void dfs(int idx, int par, int d){
    table[0][idx] = par;
    dep[idx] = d;
    for(auto & to : g[idx]){
      if(to != par) dfs(to, idx, d+1);
    }
  }

  void build(){
    dfs(0,-1,0);
    rep(k,LOG-1){
      rep(i,table[k].size()){
        if(table[k][i] == -1) table[k+1][i] = -1;
        else table[k+1][i] = table[k][table[k][i]];
      }
    }
  }

  int query(int u, int v){
    if(dep[u] > dep[v])swap(u,v);
    per(i,LOG) if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
    if(u==v) return u;
    per(i,LOG){
      if(table[i][u] != table[i][v]){
        u = table[i][u];
        v = table[i][v];
      }
    }
    return table[0][u];
  }
};


vector<vector<int> > makeTree(const vector<vector<int> > &G){
 vector<vector<int> > Tree(V);
 set<int> st;
 queue<int> que;
 que.push(0);
 st.insert(0);
 while(!que.empty()){
   int cur = que.front();que.pop();
   for(const int & v : G[cur]){
     if(st.count(v))continue;
     st.insert(v);
     que.push(v);
     Tree[cur].push_back(v);
   }
 }
 return Tree;
}

void outTree(const vector<vector<int> > &Tree){
  queue<int> que;
  que.push(0);
  while(!que.empty()){
    int cur = que.front();que.pop();
    for(const int &v : Tree[cur]){
      cout << cur SP v << endl;
      que.push(v);
    }
  }
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cin >> V;
  rep(i,V-1){
    int v,u;cin >> v >> u;
    --v,--u;
    G[v].push_back(u);
    G[u].push_back(v);
  }
  vector<vector<int> > Tree = makeTree(G);
  DoublingLowestCommonAncestor< vector<vector<int> > > lca(Tree);
  lca.build();
  int Q;cin >> Q;
  while(Q--){
    int u,v;cin >> u >> v;
    --u;--v;
    cout << lca.dep[u] + lca.dep[v] - 2*lca.dep[lca.query(u,v)] + 1 << endl;
  }
  //outTree(Tree);
  //rep(v,V)cout << lca.dep[v] SPF;
  //cout << endl;
  return 0;
}

Submission Info

Judge Result