Envío 6844

Código

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

typedef long long ll;
typedef pair<int, int> ii;
#define pb push_back
#define ff first
#define ss second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define forn(i, n) for (int i = 0; i < n; ++i)
#define rforn(i, n) for (int i = n; i >= 0; --i)
#define form(i, n, m, x) for (int i = n; i < m; i += x)
#define rform(i, n, m, x) for (int i = n; i >= m; i -= x)

#ifdef LOCAL
  #include "/debug/debug.h"
#else
  #define dbg(x...)
  #define endl '\n'
#endif

struct LCA {
  vector<int> height, euler, first, segtree;
  int n;

  LCA(vector<vector<int>> &g, int root = 0) {
    n = sz(g);
    height.resize(n);
    first.resize(n);
    dfs(g, root, root);
    int m = sz(euler);
    segtree.resize(m * 4);
    build(1, 0, m - 1);
  }

  void dfs(vector<vector<int>> &g, int v, int p, int h = 0) {
    height[v] = h;
    first[v] = sz(euler);
    euler.pb(v);
    for (int &u : g[v]) {
      if (u == p) continue;
      dfs(g, u, v, h + 1);
      euler.pb(v);
    }
  }

  void build(int node, int b, int e) {
    if (b == e) {
      segtree[node] = euler[b];
    } else {
      int mid = (b + e) / 2;
      build(node << 1, b, mid);
      build(node << 1 | 1, mid + 1, e);
      int l = segtree[node << 1], r = segtree[node << 1 | 1];
      segtree[node] = (height[l] < height[r]) ? l : r;
    }
  }

  int query(int node, int b, int e, int L, int R) {
    if (b > R || e < L) return -1;
    if (b >= L && e <= R) return segtree[node];
    int mid = (b + e) >> 1;
    int left = query(node << 1, b, mid, L, R);
    int right = query(node << 1 | 1, mid + 1, e, L, R);
    if (left == -1) return right;
    if (right == -1) return left;
    return height[left] < height[right] ? left : right;
  }

  int lca(int u, int v) {
    int left = first[u], right = first[v];
    if (left > right) swap(left, right);
    return query(1, 0, sz(euler) - 1, left, right);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  vector<vector<int>> g(n);
  forn (i, n - 1) {
    int v, u; cin >> v >> u;
    g[v].pb(u);
  }
  LCA l(g);
  int q; cin >> q;
  while (q--) {
    int v, u; cin >> v >> u;
    cout << (l.lca(v, u) == v ? "Yes" : "No") << endl;
  }
  return 0;
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */