大概思路是这样的：
利用 Euler Tour Technique 将LCA转化为 +1/-1 RMQ
利用 Method of Four Russians 将RMQ以\(\frac{\log{n}}{2}\)为大小分块（这边钦定了块大小为\(8\)），最多只有\(O(\sqrt{n})\)种块，然后预处理。
块外使用ST表来进行查询
实际查询效率并没有不分块来得优越。
quite complicated and not applicable in practice
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
template<typename T>
inline void gi(T &dx)
{
dx = 0;
int cc = getchar();
bool nega = false;
while (cc < '0' || cc > '9') { nega = (cc == '-' ? true : nega); cc = getchar(); }
while (cc >= '0' && cc <= '9') { dx = (T)(dx * 10 + cc - '0'); cc = getchar(); }
if (nega) { dx = -dx; }
}
#if __cplusplus >= 201103L || (defined(_MSVC_LANG) && _MSVC_LANG >= 201103L)
template<typename T, typename ...Args> inline void gi(T &a, Args &...args)
{ gi(a); gi(args...); }
#else
template<typename T1, typename T2> inline void gi(T1 &a, T2 &b) { gi(a); gi(b); }
template<typename T1, typename T2, typename T3> inline void gi(T1 &a, T2 &b, T3 &c) { gi(a); gi(b); gi(c); }
template<typename T1, typename T2, typename T3, typename T4> inline void gi(T1 &a, T2 &b, T3 &c, T4 &d) { gi(a); gi(b); gi(c); gi(d); }
template<typename T1, typename T2, typename T3, typename T4, typename T5> inline void gi(T1 &a, T2 &b, T3 &c, T4 &d, T5 &e) { gi(a); gi(b); gi(c); gi(d); gi(e); }
#endif
#ifdef _MSVC_LANG
#define __attribute__(x)
#else
#define log2(x) (31-__builtin_clz(x))
#endif
namespace io
{
#define BUF_SIZE 5000010
char buf[BUF_SIZE];
int at = BUF_SIZE;
FILE *in = stdin;
__attribute__((optimize("Ofast"), target("no-ieee-fp,arch=amdfam10")))inline char gc()
{
if (at == BUF_SIZE) { fread(buf, BUF_SIZE, 1, in); at = 0; }
return buf[at++];
}
template<typename T>
__attribute__((optimize("Ofast"), target("no-ieee-fp,arch=amdfam10")))inline void gi(T&n)
{
n = 0; char c = gc();
while (c<'0')c = gc();
while (c >= '0') { n = n * 10 - 48 + c; c = gc(); }
}
#if __cplusplus >= 201103L || (defined(_MSVC_LANG) && _MSVC_LANG >= 201103L)
template<typename T, typename ...Args> inline void gi(T &a, Args &...args)
{ gi(a); gi(args...); }
#else
template<typename T1, typename T2> inline void gi(T1 &a, T2 &b) { gi(a); gi(b); }
template<typename T1, typename T2, typename T3> inline void gi(T1 &a, T2 &b, T3 &c) { gi(a); gi(b); gi(c); }
template<typename T1, typename T2, typename T3, typename T4> inline void gi(T1 &a, T2 &b, T3 &c, T4 &d) { gi(a); gi(b); gi(c); gi(d); }
template<typename T1, typename T2, typename T3, typename T4, typename T5> inline void gi(T1 &a, T2 &b, T3 &c, T4 &d, T5 &e) { gi(a); gi(b); gi(c); gi(d); gi(e); }
#endif
char str[BUF_SIZE * 10]; int len, out[100], num;
template<typename T>
__attribute__((optimize("Ofast"), target("no-ieee-fp,arch=amdfam10")))inline void wi(T k)
{ num = 0; do { out[++num] = k % 10, k /= 10; } while (k); for (int i = num; i >= 1; --i)str[len++] = '0' + out[i]; str[len++] = '\n'; }
#undef BUF_SIZE
};
const int maxn = 111111;
int n, m;
struct graph
{
int beg[maxn], nxt[maxn * 2], to[maxn * 2];
int e;
void ae(int x, int y)
{
++e;
to[e] = y;
nxt[e] = beg[x];
beg[x] = e;
}
} g;
int fa[maxn];
int dep[maxn];
int rt;
int eu[maxn * 2], ec = 0;
int rv[maxn * 2];
int any[maxn * 2];
const int lay = 18;
int st[33333][lay + 2];
int rm[33333][9][9];
int pre[33333][9];
int suf[33333][9];
int inn[33333];
int typ[33333];
int tv[33333];
const int bs = 8;
int gn;
#define bel(x) ((((x)-1)>>3)+1)
inline void build_rmq(int nn)
{
static int a[233];
while ((nn & 7) != 0) ++nn;
for (int i = 0; i < (1 << (bs - 1)); ++i) { // 0:-1, 1:+1
a[1] = 0;
for (int j = 0; j < bs - 1; ++j) {
if (i & (1 << j)) {
a[j + 2] = a[j + 1] + 1;
} else {
a[j + 2] = a[j + 1] - 1;
}
}
for (int j = 1; j <= bs; ++j) {
rm[i][j][j] = j;
for (int k = j + 1; k <= bs; ++k) {
rm[i][j][k] = a[k] < a[rm[i][j][k - 1]] ? k : rm[i][j][k - 1];
}
}
for (int j = 1; j <= bs; ++j) {
pre[i][j] = rm[i][1][j];
suf[i][j] = rm[i][j][bs];
}
inn[i] = rm[i][1][bs];
}
gn = nn >> 3;
for (int i = 1; i <= gn; ++i) {
// i * bs - bs + 1 -> i * bs
typ[i] = 0;
int upl = i << 3;
for (int j = upl - bs + 2, cc = 0; j <= upl; ++j, ++cc) {
if (rv[j] - rv[j - 1] >= 0) {
typ[i] |= (1 << cc);
}
}
tv[i] = rv[inn[typ[i]] + ((i - 1) << 3)];
}
int lly = log2(gn) + 1;
for (int i = 1; i <= gn; ++i) { st[i][0] = i; }
for (int j = 1; j <= lly; ++j) {
// i + 2^j - 1 <= n
// i <= n - 2^j + 1
int upl = gn - (1 << j) + 1;
//cerr << upl << endl;
for (int i = 1; i <= upl; ++i) {
int k = i + (1 << (j - 1));
st[i][j] = tv[st[k][j - 1]] < tv[st[i][j - 1]] ? st[k][j - 1] : st[i][j - 1];
}
}
}
inline int stq(int l, int r)
{
++r;
int dis = r - l;
int p = log2(dis);
r -= 1 << p;
return tv[st[l][p]] < tv[st[r][p]] ? st[l][p] : st[r][p];
}
inline int rmq(int l, int r)
{
if (l > r) swap(l, r);
int ll = bel(l), rr = bel(r);
if (ll == rr) {
int bas = (ll - 1) << 3;
int dl = l - bas, dr = r - bas;
return bas + rm[typ[ll]][dl][dr];
} else if (ll + 1 == rr) {
int lb = (ll - 1) << 3, rb = (rr - 1) << 3;
int i1 = suf[typ[ll]][l - lb] + lb;
int i2 = pre[typ[rr]][r - rb] + rb;
return rv[i1] < rv[i2] ? i1 : i2;
} else {
int tt = stq(ll + 1, rr - 1);
tt = ((tt - 1) << 3) + inn[typ[tt]];
int lb = (ll - 1) << 3, rb = (rr - 1) << 3;
int i1 = suf[typ[ll]][l - lb] + lb;
int i2 = pre[typ[rr]][r - rb] + rb;
int ii = rv[i1] < rv[i2] ? i1 : i2;
return rv[ii] < rv[tt] ? ii : tt;
}
}
void dfs(int x)
{
eu[++ec] = x;
any[x] = ec;
for (int i = g.beg[x]; i; i = g.nxt[i]) {
int y = g.to[i];
dep[y] = dep[x] + 1;
dfs(y);
eu[++ec] = x;
}
}
inline int lca(int x, int y)
{
return eu[rmq(any[x], any[y])];
}
int main()
{
//freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
io::gi(n);
for (int i = 1; i < n; ++i) {
int a, b; io::gi(a, b);
fa[b] = a;
g.ae(a, b);
}
for (int i = 1; i <= n; ++i) {
if (fa[i] == 0) {
fa[i] = i;
rt = i;
break;
}
}
dfs(rt);
for (int i = 1; i <= ec; ++i) { rv[i] = dep[eu[i]]; }
build_rmq(ec);
io::gi(m);
for (int i = 1; i <= m; ++i) {
int x, y;
io::gi(x, y);
io::wi(lca(x, y));
}
fwrite(io::str, io::len, 1, stdout);
return 0;
}