首先假设我们不考虑 u 和 v 两点的缆车，那么 x 和 y 之间的路程就是 x 和 y 的深度减去他们的 lca 的深度。

接下来我们考虑使用缆车，无非也就两种情况：

  • x -> u -> v -> y
  • x -> v -> u -> y

我们对上面三种情况取一个 min 就行了。

加快读的话可以跑到 600 ms

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
const int maxn = 301110;
const int M = 1e9+7;
int n,q,xx,yy;

vector<int> v[maxn];

int sz[maxn],fa[maxn],d[maxn],son[maxn];

void dfs1(int u,int pre)
{
    sz[u] = 1;fa[u] = pre;d[u] = d[pre]+1;
    for(auto i : v[u])
    {
        if(i == pre) continue;
        dfs1(i,u);
        sz[u] += sz[i];
        if(sz[son[u]] < sz[i]) son[u] = i;
    }
}

int top[maxn],idx;

void dfs2(int u,int t)
{
    top[u] = t;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(auto i : v[u])
    {
        if(i == fa[u] || i == son[u]) continue;
        dfs2(i,i);
    }
}

int lca(int x,int y)
{
    for(;top[x] != top[y];d[top[x]]>d[top[y]]?x=fa[top[x]]:y=fa[top[y]]);
    return d[x]<d[y]?x:y;       //在一条链上了
}

int dis(int x,int y)
{
    return d[x]+d[y]-2*d[lca(x,y)];
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    int x,y;
    for(int i = 1; i < n; i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs1(1,1);dfs2(1,1);
    cin>>xx>>yy;
    cin>>q;
    while(q--)
    {
        cin>>x>>y;
        int ans = dis(x,y);
        ans = min(ans,dis(x,xx)+dis(y,yy));
        ans = min(ans,dis(x,yy)+dis(y,xx));
        cout<<ans<<endl;
    }
    return 0;
}