小A的最短路

小A的最短路

https://ac.nowcoder.com/acm/problem/23482
题意：给你一颗树，问你dis（x,y）,其中有个特殊通道dx----->dy的dis=0，Q次询问问你dis（u,v);
思路：首先没有这个限制条件我们直接求dis(u,v)就行，有了这个条件我们需要考虑是否走dx--->dy;那么会新增几条路，u->dx->dy->v或者u->dy->dx->v;直接算一下取最小值即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e15+7;
const int N=4e5+5;
const int M=1e6+5;
int f[N][30],d[N];
struct node {
    int to,w;
};
vector<node>G[N];
int n,m,dep;
void bfs() {
    queue<node>q;
    q.push({1,1});
    d[1]=1;
    dep=(int)(log(n)/log(2))+1;
    while(!q.empty()) {
        int u=q.front().to;
        q.pop();
        int len=G[u].size();
        for(int i=0; i<len; i++) {
            int v=G[u][i].to,w=G[u][i].w;
            if(d[v])
                continue;
            d[v]=d[u]+w;
            f[v][0]=u;
            for(int j=1; j<=20; j++)
                f[v][j]=f[f[v][j-1]][j-1];
            q.push({v,d[v]});
        }
    }
}
int LCA(int x,int y) {
    if(d[x]<d[y])
        swap(x,y);
    for(int i=20; i>=0; i--) {
        if(d[f[x][i]]>=d[y])
            x=f[x][i];
    }
    if(x==y)
        return x;
    for(int i=20; i>=0; i--) {
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    }
    return f[x][0];
}
int dx,dy;
int dist(int x,int y)
{
    int fa=LCA(x,y);
    return d[x]+d[y]-2*d[fa];
}
int main() {
    cin>>n;
    for(int j=1; j<n; j++) {
        int u,v,w;
        scanf("%d%d",&u,&v);
        G[u].push_back({v,1});
        G[v].push_back({u,1});
    }
    bfs();
    cin>>dx>>dy;
    cin>>m;
    while(m--) {
        int x,y;
        scanf("%d%d",&x,&y);
        int dis=dist(x,y);
        dis=min(dist(x,dy)+dist(y,dx),dis);
        dis=min(dist(x,dx)+dist(y,dy),dis);
        printf("%d\n",dis);
    }

}