题目描述

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

输入描述:

第一行一个整数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消耗的最少体力对于每个询问下x,y输出一个结果，代表x到y消耗的最少体力

题解

LCA

由题目中的数据我们可以看出这个图是一棵树，两点之间的最短路径是唯一的，很自然的想到x和y点的距离就是dep[x]+dep[y]-2*dep[lca(x,y)]

题目中又有一个u和v之间不用消耗体力的条件，那每次询问就是在x->y，x->u->v->y，x->v->u->y三个距离之间找一个最小的就可以了

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=3e5+100;
int dp[N][30],dep[N];
vector<int> v[N];
void dfs(int node,int fa){
    dep[node]=dep[fa]+1;
    dp[node][0]=fa;
    for(int i=1;(1<<i)<=dep[node];++i){
        dp[node][i]=dp[dp[node][i-1]][i-1];
    }
    for(int i=0,len=v[node].size();i<len;++i){
        if(v[node][i]==fa)continue;
        dfs(v[node][i],node);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    int tem=dep[x]-dep[y];
    for(int j=0;tem;++j){
        if(tem&1)x=dp[x][j];
        tem>>=1;
    }
    if(x==y)return x;
    for(int j=29;j>=0&&x!=y;--j){
        if(dp[x][j]!=dp[y][j]){
            x=dp[x][j];
            y=dp[y][j];
        }
    }
    return dp[x][0];
}
int cross(int x,int y){
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}
////////////////////////////////////////////////////////////////////////
int main(){
    int n=gn();
    repi(i,2,n){
        int x=gn(),y=gn();
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1,0);
    int l=gn(),r=gn();
    int q=gn();
    while(q--){
        int x=gn(),y=gn();
        int ans=min(cross(x,y),min(cross(x,l)+cross(r,y),cross(x,r)+cross(l,y)));
        print(ans),putchar(10);
    }
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/