Submission #1756000

---

Source Code Expand

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

template<typename T> T inf;
template<> constexpr int inf<int> = 1e9;
template<> constexpr ll inf<ll> = 1e18;
template<> constexpr ld inf<ld> = 1e30;

class LCA {
  int size, log_size;
  vector<vector<int>> parent;
  vector<int> depth;
  template <typename Edge>
  void dfs(const vector<vector<Edge>> &g, int v, int p, int d) {
    parent[0][v] = p; depth[v] = d;
    for (const Edge &e: g[v]) {
      if (e.to != p) dfs(g, e.to, v, d + 1);
    }
  }
public:
  template <typename Edge>
  LCA(const vector<vector<Edge>> &g, int root) : size(g.size()), log_size(0), depth(size, 0) {
    for (int v = size; v > 0; v /= 2) ++log_size;
    parent.assign(log_size, vector<int>(size, 0));
    dfs(g, root, -1, 0);
    for (int k = 0; k < log_size - 1; ++k) {
      for (int v = 0; v < size; ++v) {
        if (parent[k][v] < 0) parent[k + 1][v] = -1;
        else parent[k + 1][v] = parent[k][parent[k][v]];
      }
    }
  }
  int query(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < log_size; ++k)
      if (((depth[v] - depth[u]) >> k) & 1) v = parent[k][v];
    if (u == v) return u;
    for (int k = log_size - 1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
};

template <typename Edge>
vector<typename Edge::Cost> bfs01(const vector<vector<Edge>> &g, int s) {
  using Cost = typename Edge::Cost;
  vector<Cost> d(g.size(), inf<Cost>);
  d[s] = 0;
  deque<pair<Cost,int>> que;
  que.emplace_back(0, s);
  while (!que.empty()) {
    auto top = que.front();
    que.pop_front();
    Cost dist = top.first; int v = top.second;
    if (d[v] < dist) continue;
    for (const auto &e: g[v]) {
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        if (e.cost == 1) que.emplace_back(d[e.to], e.to);
        else if (e.cost == 0) que.emplace_front(d[e.to], e.to);
        else assert(false);
      }
    }
  }
  return d;
}

struct Edge {
  using Cost = int;
  int to;
  Cost cost;
  Edge(int t, Cost c) : to(t), cost(c) {}
};

using Graph = vector<vector<Edge>>;

void add_edge(Graph &g, int from, int to, Edge::Cost cost) {
  g[from].emplace_back(to, cost);
  g[to].emplace_back(from, cost);
}

int main() {
  int n, q;
  cin >> n;
  Graph g(n);
  REP(i,n-1) {
    int s, t;
    cin >> s >> t;
    --s; --t;
    add_edge(g, s, t, 1);
  }
  LCA lca(g, 0);
  auto d = bfs01(g, 0);
  cin >> q;
  REP(i,q) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    int v = lca.query(a, b);
    cout << d[a] + d[b] - d[v] * 2 + 1 << endl;
  }
  return 0;
}

Submission Info

Judge Result