前言：一开始看到这个题目的时候，感觉就和lca有关，但是没有想到具体的公式

$d=dep[x]+dep[y]-2\ast dep[lca(x,y)]$

并且我们这个题目还是一个进阶版本的题，我们还会存在电缆，我们还有两种选择的可能，这也是要考虑在内的

---

题目地址

#include <bits/stdc++.h>
using namespace std;
#define ll long longconst int N = (int)5e5;
int n;
int e[N * 2], ne[N * 2], h[N], idx = 0;
int px, py;
int dep[N], fa[N][20];inline int read()
{int x = 0, f = 1;char c = getchar();while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();return f * x;
}void add(int a, int b) {e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}void dfs(int u, int father) {dep[u] = dep[father] + 1;fa[u][0] = father;for (int i = 1; i < 20; i++) {fa[u][i] = fa[fa[u][i - 1]][i - 1];}for (int i = h[u]; i; i = ne[i]) {int to = e[i];if (to == father) continue;dfs(to, u);}
}int lca(int u, int v) {if (dep[u] < dep[v]) swap(u, v);// 先跳到同一层for (int i = 19; i >= 0; i--) {if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];}if (u == v) return u;for (int i = 19; i >= 0; i--) {if (fa[u][i] != fa[v][i]) {u = fa[u][i], v = fa[v][i];}}return fa[u][0];
}int fun(int x, int y) {return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}int main() {cin >> n;for (int i = 1; i < n; i++) {int x, y; //cin >> x >> y;x = read(); y = read();add(x, y), add(y, x);}cin >> px >> py;int q; cin >> q;dfs(1, 0);while (q--) {int x, y; //cin >> x >> y;x = read(); y = read();int d = min({ fun(x,y),fun(x,px) + fun(y,py),fun(x,py) + fun(y,px) });//cout << d << endl;printf("%d\n", d);}return 0;
}