题意：
给你一棵树包含n个顶点，和n-1条边。在这棵树的基础上再加一条边。求树上两个顶点之间的距离。

题解：
其实有题意我们很容易想到要求两个顶点之间的LCA,从而间接求解两个顶点之间的最短距离。
1.首先我们考虑不做缆车，那就是求dist(x,y)
2.我们在考虑做缆车的情况，但是有分两种情况
2.1从x走到u做缆车，dist(x,u)+dist(v,y)
2.2从x走到v做缆车，dist(x,v)+dist(u,y)
综上，ans=min(dist(x,y),dist(x,u)+dist(v,y),dist(x,v)+dist(u,y))

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int n,qu,root,Dep[maxn],fa[maxn],ans,in[maxn];
vector<int>vec[maxn];
struct node{
    int id,dep;
};
void bfs(){
    int i,id,lenV;
    node now;
    queue<node>qu;
    qu.push({root,0});
    while(!qu.empty()){
        now=qu.front(),qu.pop();Dep[now.id]=now.dep;
        lenV=vec[now.id].size();
        for (i=0;i<lenV;i++){
            id=vec[now.id][i];
            qu.push({id,now.dep+1});
        }
    }
}
int lca(int x,int y){
    if(x==y)return x;
    if(Dep[x]<Dep[y])swap(x,y);
    while(Dep[x]>Dep[y])x=fa[x];
    if(x==y)return x;
    while(x!=root){
        x=fa[x],y=fa[y];
        if(x==y)return x;
    }
    return root;
}
int main()
{
    int i,j,k,u,v,x,y;
    while(scanf("%d",&n)!=EOF){
        memset(in,0,sizeof(in));
        for (i=1;i<=300000;i++)vec[i].clear();
        for (i=n-1;i>=1;i--){
            scanf("%d%d",&u,&v);
            if(u>v)swap(u,v);
            fa[v]=u,vec[u].push_back(v);in[v]++;
        }
        scanf("%d%d",&u,&v);
        if(u>v)swap(u,v);
        for (i=1;i<=n;i++){
            if(in[i]==0){
                root=i;break;
            }
        }
        bfs();
        scanf("%d",&qu);
        while(qu--){
            scanf("%d%d",&x,&y);
            if(x>y)swap(x,y);
            ans=Dep[x]+Dep[y]-2*Dep[lca(x,y)];
            ans=min(ans,Dep[x]+Dep[u]-2*Dep[lca(x,u)]+Dep[v]+Dep[y]-2*Dep[lca(v,y)]);
            ans=min(ans,Dep[x]+Dep[v]-2*Dep[lca(x,v)]+Dep[u]+Dep[y]-2*Dep[lca(u,y)]);
            printf("%d\n",ans);
        }
    }
    return 0;
}