Submission #1756123

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
template <typename T, typename Updater>
class SegmentTree{
  int N;
  vector<T> tree;
  Updater updater;
public:
  SegmentTree(){;}
  SegmentTree(int n, Updater f) : updater(f) {
    N = 1;
    while(N < n) N *= 2;
    tree.resize( 2 * N - 1, updater.dflt);
  }
  SegmentTree(int n, Updater f, vector<T> &vs) : updater(f) { // vsで初期化
    N = 1;
    while(N < n) N *= 2;
    tree.resize( 2 * N - 1, updater.dflt );
    int i;
    for(i = 0; i < vs.size(); i++)
      tree[i + N - 1] = vs[i];
    for(int k = N - 2; k >= 0; k--){
      tree[k] = updater.merge(tree[2 * k + 1], tree[2 * k + 2]);
    }
  }
  void update(int k, T a){
    k += N - 1;
    updater.update(tree[k], a);
    while(k > 0){
      k = (k-1) / 2;
      tree[k] = updater.merge(tree[2 * k + 1], tree[2 * k + 2]);
    }
  }
  T query(int a, int b, int k, int l, int r){
    if( r <= a || b <= l ) return updater.dflt;
    if( a <= l && r <= b ) return tree[k];
    return updater.merge( query(a, b, 2 * k + 1, l, (r + l) / 2),
			  query(a, b, 2 * k + 2, (r + l) / 2, r) );
  }
  T query(int a, int b){ return query(a, b, 0, 0, N); }
};
typedef vector< vector<int> > Graph;
typedef pair<int,int> P;
class RMQi{
public:
  P dflt;
  RMQi(){ dflt = P(1e9,-1); }
  P merge(P l, P r){ return min(l,r); }
  P update(P &node, P v){ node = v; }
};
class LCA{
public:
  int V, root;
  bool inited;
  Graph G;
  vector<int> vs;
  vector<int> depth;
  vector<int> id;
  SegmentTree<P, RMQi > rmq;
  LCA(int V, int r) : V(V), root(r) {
    inited = false;
    G.resize(V);
    vs.resize(2 * V + 1);
    depth.resize(2 * V + 1);
    id.resize(V);
  }
  void add_edge(int v, int u){
    G[v].push_back(u);
    G[u].push_back(v);
  }
  void lca_init(){
    inited = true;
    int k = 0;
    dfs(root, -1, 0, k);
    vector<P> d(2*V+1);
    for(int i = 0; i < 2 * V + 1; i++)
      d[i] = P(depth[i], i);
    rmq = SegmentTree<P, RMQi > ( 2 * V + 1, RMQi(), d );
  }
  void dfs(int v, int p, int d, int &k){
    id[v] = k;
    vs[k] = v;
    depth[k++] = d;
    for(int i = 0; i < G[v].size(); i++){
      int u = G[v][i];
      if( u != p ){
	dfs(u, v, d + 1, k);
	vs[k] = v;
	depth[k++] = d;
      }
    }
  }
  int lca(int v, int u){
    if( ! inited ) lca_init();
    int minid = min(id[v],id[u]);
    int maxid = max(id[v],id[u]);
    P p = rmq.query(minid, maxid + 1);
    return vs[ rmq.query( minid , maxid + 1 ).second ];
  }
};

int h[100001];
bool used[100001];
void bfs( LCA & lca ){
  queue<P> Q;
  Q.push(P(0,0));
  used[0] = true;
  while( !Q.empty() ){
    int v = Q.front().first;
    int d = Q.front().second; Q.pop();
    h[v] = d;
    for(int i = 0; i < lca.G[v].size(); i++){
      int u = lca.G[v][i];
      if( ! used[u] ){
	used[u] = true;
	Q.push( P( u, d + 1 ) );
      }
    }
  }
}

int main(){
  int N;
  cin >> N;
  LCA lca(N, 0);
  for(int i = 0; i < N-1; i++){
    int a, b;
    cin >> a >> b;
    a--; b--;
    lca.add_edge(a,b);
  }
  lca.lca_init();
  bfs( lca );
  //cout << "ok" << endl;
  int Q;
  cin >> Q;
  for(int i = 0; i < Q; i++){
    int a, b;
    cin >> a >> b;
    a--; b--;
    //cout << a << " " << b << endl;
    int c = lca.lca(a,b);
    //cout << c << endl;
    int ans = h[a] + h[b] - 2 * h[c] + 1;
    cout << ans << endl;
  }
}

Submission Info

Judge Result