Submission #7550128

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

# define REP(i,n) for (int i=0;i<(n);++i)
# define PER(i,n) for (int i=(N-1);i>=0;--i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ll;
typedef pair<double,double> P_dd;

const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
struct edge {int to , cost;};
typedef vector<vector<edge>> wgraph; // cost, to


void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

vector<ll> dijkstra(wgraph G,int s){
    priority_queue<P_ll, vector<P_ll>, greater<P_ll>> que;
    vector<ll> dist(G.size(),longinf);

    dist[s] = 0;
    que.push({0LL, s});

    while(!que.empty()){
        P_ll p = que.top();que.pop();

        ll v = p.second,d = p.first;
        if(dist[v] < d) continue;
        for(auto e : G[v]){
            if(dist[e.to] > dist[v] + e.cost){
                dist[e.to] = dist[v] + e.cost;
                que.push({dist[e.to], e.to});
            }
        }
    }
    return dist;
}

struct DoublingLowestCommonAncestor {
  const int LOG;
  vector< int > dep;
  const wgraph &g;
  vector< vector< int > > table;

  DoublingLowestCommonAncestor(const wgraph &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.to != par) dfs(to.to, idx, d + 1);
    }
  }

  void build() {
    dfs(0, -1, 0);
    for(int k = 0; k + 1 < LOG; k++) {
      for(int i = 0; i < table[k].size(); i++) {
        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);
    for(int i = LOG - 1; i >= 0; i--) {
      if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
    }
    if(u == v) return u;
    for(int i = LOG - 1; i >= 0; i--) {
      if(table[i][u] != table[i][v]) {
        u = table[i][u];
        v = table[i][v];
      }
    }
    return table[0][u];
  }
};

int main() {
    int N;
    cin >> N;

    wgraph w(N);
    REP(i, N - 1){
        int x, y;
        cin >> x >> y;
        w[x - 1].push_back({y - 1, 1});
        w[y - 1].push_back({x - 1, 1});
    }
    auto dist = dijkstra(w, 0);

    int Q;
    cin >> Q;
    vector<P_ll> q(Q);
    REP(i, Q){
        cin >> q[i].first >> q[i].second;
        q[i].first--;
        q[i].second--;
    }

    DoublingLowestCommonAncestor lca(w);
    lca.build();

    REP(i, Q){
        int a = lca.query(q[i].first, q[i].second);
        cout << dist[q[i].first] + dist[q[i].second] - 2 * dist[a] + 1 << endl;
    }

	return 0;
}

Submission Info

Judge Result