题目描述:
小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去的那个地方，他最少要消耗的体力值是多少。
链接：https://ac.nowcoder.com/acm/problem/23482
来源：牛客网

输入描述:
第一行一个整数N代表景区的个数。
接下来N-1行每行两个整数u,v代表从位置u到v之间有一条路径可以互相到达。
接下来的一行两个整数U,V表示这两个城市之间可以直接坐缆车到达。
接下来一行一个整数Q，表示有Q次询问。
接下来的Q行每行两个整数x,y,代表小A的位置在x，而他想要去的地方是y。
输出描述:
对于每个询问下x,y输出一个结果，代表x到y消耗的最少体力对于每个询问下x,y输出一个结果，代表x到y消耗的最少体力。

思路：看到这题要注意有N-1条路径，这说明这是一颗树，那我们就可以利用lca来求两点之间的最短路，用两点到根的距离减去两倍lca到根的距离。答案需要考虑三种情况，不坐电缆，坐电缆u，做电缆v，分别求出答案再求最小值即可。

代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector<int> g[400005];
int dep[400005],f[400005][100],lg[400005];
int dist[400005];
//f[i][j]表示i往上走2^j步到达的点
void dfs(int u,int fa){

    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int j=1;(1<<j)<=dep[u];j++)//u的2^(j-1)祖先的2^(j-1)祖先
        f[u][j]=f[f[u][j-1]][j-1];
    for(int i=0;i<(int)g[u].size();i++){
        int v=g[u][i];
        if(v!=fa){
            dist[v]=dist[u]+1;
            dfs(v,u);
        }
    }
}
void init(int n){
    for(int i=1;i<=n;i++)//预处理出log2(i)+1的值,便于直接调用
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);//不妨设u的深度 >= v的深度,便于下面统一处理
    while(dep[u]>dep[v])u=f[u][lg[dep[u]-dep[v]]-1];//跳到统一深度
    if(u==v)return u;
    for(int j=lg[dep[u]]-1;j>=0;j--)//从步数大往小的跳
        if(f[u][j]!=f[v][j])//因为我们要跳到它们LCA的下面一层，所以它们肯定不相等，如果不相等就跳过去
            u=f[u][j],v=f[v][j];
    return f[u][0];//返回父节点
}


int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    init(n);
    dist[1]=0;
    dfs(1,0);
    int u,v;
    scanf("%d%d",&u,&v);
    int q;
    scanf("%d",&q);
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        int id=lca(x,y);
        int ans=dist[x]+dist[y]-2*dist[id];
        int id1=lca(x,u),id2=lca(y,v);
        ans=min(ans,dist[x]+dist[u]-2*dist[id1]+dist[y]+dist[v]-2*dist[id2]);
        id1=lca(x,v),id2=lca(y,u);
        ans=min(ans,dist[x]+dist[v]-2*dist[id1]+dist[y]+dist[u]-2*dist[id2]);
        printf("%d\n",ans);
    }
    return 0;
}