小A的最短路 | LCA

首先题目给出是一棵树

我们可以知道树上两点路径唯一

其次又有一条额外免费的边

所以我们可以这么考虑，x,y之间的路径要么是 在原树上由x到y，要么经过额外免费的边

对于每个询问，取三种情况最小值即可

ll n,m,p;
struct node{
    int e,next;
}edge[maxn];
int head[maxn];
int deep[maxn];
int f[maxn][21];
ll cnt = 0;
void addedge(int u,int v){
    edge[cnt] = node{v,head[u]};
    head[u] = cnt ++;
}
void dfs(int u,int fa){
    deep[u]=deep[fa]+1;
    f[u][0]=fa;
    for(int i=1;(1<<i)<=deep[u];i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];~i;i=edge[i].next){
        int e=edge[i].e;
        if(e!=fa) dfs(e,u);
    }
}
int LCA(int u,int v)
{
    if(deep[u]<deep[v]) swap(u,v);
    for(int i=19;i>=0;i--)   if(deep[f[u][i]]>=deep[v]) u=f[u][i];//比他深往上跳
    if(u==v) return u;
    for(int i=19;i>=0;i--){
        if(f[u][i]!=f[v][i]){//因为从同一深度开始向上跳 一样有可能是更远的祖先
            u=f[u][i];
            v=f[v][i];
        }
    }
    return f[u][0];//随便返回一个上一级即可
}
ll dis(int u,int v){
    return deep[u] + deep[v] - 2*deep[LCA(u,v)];
}
int main()
{
    memset(head,-1,sizeof(head));
    read(n);
    for(int i=1;i<=n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);addedge(y,x);
    }
    for(int i=1;i<=n;i++)
        if(!deep[i]) dfs(i,i);
    ll sx,sy;read(sx);read(sy);
    read(m);
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        printf("%lld\n",min(dis(x,y),min(dis(x,sx)+dis(sy,y),dis(x,sy)+dis(sx,y))));
    }
    return 0;
}