小A的最短路 LCA

题目描述：
小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去的那个地方，他最少要消耗的
体力值是多少。
题解：可以理解为LCA的模板题了，因为他N个点只有N-1条边，所以是一棵树，但是这个题有一个比较特别的地方，有两个点之间是不需要花体力就可以到达的，这样的话我们就多了在模板题的基础上，也就是他在这棵树上搭了一个通道，所以只需要每次特判一下是否通过这个通道会更近即可也就是

dis(u,v)
dis(u,x)+dis(v,y)
dis(u,y)+dis(v,x)

这三者之间的最小值。

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <string>
const int maxn = 1e6+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;
const int maxlog=20;
struct node{
    int to,next;
}edge[maxn];

int head[maxn],cnt=1;
int deep[maxn];
int fa[maxn][maxlog+1];

inline void add(int u,int v){
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs(int root,int father){
    //cout<<root<<endl;
    fa[root][0]=father;
    deep[root]=deep[father]+1;
    for(int i=1;(1<<i)<=deep[root];i++){
        fa[root][i]=fa[fa[root][i-1]][i-1];
    }
    for(int i=head[root];i;i=edge[i].next){
        if(edge[i].to==father) continue;
        dfs(edge[i].to,root);
    }
}

int lca(int x,int y){
    if(deep[x]>deep[y]) swap(x,y);
    for(int i=maxlog;i>=0;i--){
        if(fa[y][i]!=-1&&deep[fa[y][i]]>=deep[x]){
            y=fa[y][i];
        }
    }
    if(x==y) return x;
    for(int i=maxlog;i>=0;i--){
        if(fa[x][i]!=-1&&fa[y][i]!=-1&&fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
inline int dis(int u,int v){
    return deep[u]+deep[v]-2*deep[lca(u,v)];
}
int main(){
    //memset(head,-1,sizeof head);
    //memset(fa,-1,sizeof fa);
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    int x,y;
    cin>>x>>y;
    int q;
    cin>>q;
    while(q--){
        int u,v;
        scanf("%d%d",&u,&v);
        int ans=dis(u,v);
        ans=min(ans,dis(u,x)+dis(v,y));
        ans=min(ans,dis(u,y)+dis(v,x));
        printf("%d\n",ans);
    }
    return 0;

}