【每日一题】小A的最短路

题目

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

解题思路

利用 LCA 求树上的任意两点距离。

如果不坐缆车，此时消耗体力值为 。
如果坐缆车，有 2 种情况：
① 从点 x 到达点 U，坐缆车到 V，再从 V 到达 y。此时消耗体力值为 。
① 从点 x 到达点 V，坐缆车到 U，再从 U 到达 y。此时消耗体力值为 。

取上面三种消耗体力值的最小值。

C++代码

#include<iostream>
#include<vector>
using namespace std;

vector<vector<int>> edges;
vector<int> father;
vector<int> deep;

void dfs(int s, int fa){
    father[s] = fa;
    for(auto e : edges[s]){
        if(e==fa) continue;
        deep[e] = deep[s] + 1;
        dfs(e, s);
    }
}

int lca(int a, int b){
    if(deep[a] < deep[b])
        swap(a,b);
    while(deep[a] > deep[b])
        a = father[a];
    while(a!=b){
        a = father[a];
        b = father[b];
    }
    return a;
}

int dist(int a, int b){
    int an = lca(a,b);
    int d = deep[a] + deep[b] - 2*deep[an];
    return d;
}

int main(){
    int n, q;
    cin >> n;
    edges.resize(n+1);
    deep.resize(n+1,0);
    father.resize(n+1,0);
    int u, v;
    for(int i=0; i<n-1; ++i){
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    dfs(1,0);
    int U, V;
    cin >> U >> V;
    cin >> q;
    int x, y;
    while(q--){
        cin >> x >> y;
        int d = dist(x,y);
        d = min(d, dist(x,U)+dist(V,y));
        d = min(d, dist(x,V)+dist(U,y));
        cout << d << endl;
    }
    return 0;
}