题目

题目描述：
小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消耗的最少体力

解析

1）知识点

  • 这道题是一道lcd板子题，但是我不会lcd，所以是现学现卖的（怕会写错了QAQ

2）看题目

  • 这道题就是问你树上两点最短时间，然后一个特别的地方就是有一条路可以节省时间，求最短时间。

3）算法分析

  1. 我先来说一下lcd是啥：
    1. lcd就是用来查找树上两点之间的最近公共父节点的算法。我们这里为什么用呢，因为最短路肯定要有一个相交点，所以那个点就是最近的公共父节点。
  2. 然后我们就来解释一下lcd算法是什么原理吧：
    1. 首先我们要算两个点的最近公共父节点，这时假设节点一个高，一个低（前提是按照正常树的样子放好），公共父节点一定不会在他们之间。所以我们就先讲较低的节点上移到相同的层来。
    2. 然后就是查找父节点了，这个时候只要让两个节点同时不停的往上找（一边一下），那么迟早就找到了。
  3. 知道lcd是什么原理之后，我们再将怎么去实现这个算法，我们这里用的是在线算法：lcd+倍增。
    1. 首先是实现两个节点移动到相同的层数：我们理解一下可以发现，任何一个数都可以用不重复的二的倍数相加表示。然后我们就做一个循环，假设i的最大值为20，向下循环，这样算的也快呀hh
    2. 接下来就是同时查找父节点，就查呗。
  4. 最后我还有一个没有讲到的问题就是，深度和父节点怎么求：
    1. 深度用一个deep[]数组，然后父节点用一个f[][]数组就好了，第二个维度是什么？就是ta的第2^i个父节点（就是往上查找）。

4）算法操作

  1. 然后我们就来看一下算法代码：
  2. 数组初始化： 
    void dfs(int u, int fa) {
    deep[u] = deep[fa] + 1;
    for (int i = 0; i <= 20 - 1; i++)
        f[u][i + 1] = f[f[u][i]][i];
    
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) continue;
        f[v][0] = u;
        dfs(v, u);
    }
}
  3. lca计算： 
    int lca(int x, int y) {
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 20; i >= 0; i--)
        if (deep[f[x][i]] >= deep[y])
            x = f[x][i];
    //将要计算的两个节点先换到同一层
    //因为在换节点的时候，x一直在变，所有数字都可以拆成2的倍数之和（而且不重复），所以可以换到同一层
    if (x == y) return x;
    
    for (int i = 20; i >= 0; i--)
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    //将两个节点同时上移（同步移动），
    return f[x][0];
}
  4. 最后注意一下树的距离的计算： 
    int dist(int u, int v) {
    return deep[u] + deep[v] - 2 * deep[lca(u, v)];
}

5）打代码

  1. 打代码啦！
  2. 首先是用前向星保存树的结构
  3. 然后将数组初始化了
  4. 接下来就是计算最短距离了
  5. 因为有特殊道路，所以我们先算直通的
  6. 然后和使用这个路的时间去比大小
  7. 看我代码咯~

AC代码 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int N = 3e5 + 7;
int head[N], tot;
struct EDGE {
    int u, v, w, next;
} edge[N << 1];
int deep[N], f[N][21];//节点深度，fa[i][j]为i的第2^j个祖先
//全局变量区

void init();//前向星初始化
void add_edge(int u, int v);//前向星加边
void dfs(int u, int fa);//前向星dfs
int lca(int x, int f);//搜索最近相同父节点
int dist(int u, int v);//求树两点的距离
//函数预定义区

int main() {
    IOS;
    int n; cin >> n;
    init();
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    int x, y; cin >> x >> y;
    dfs(1, 0);
    
    int T; cin >> T;
    while (T--) {
        int u, v; cin >> u >> v;
        int ans = dist(u, v);//初始化为直接路径
        ans = min(ans, dist(u, x) + dist(y, v));
        ans = min(ans, dist(u, y) + dist(x, v));
        //判断要不要去走近路
        cout << ans << endl;
    }
    return 0;
}
void init() {
    memset(head, 0, sizeof head); tot = 0;
}
void add_edge(int u, int v) {
    tot++;
    edge[tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot;
}
void dfs(int u, int fa) {
    deep[u] = deep[fa] + 1;
    for (int i = 0; i <= 20 - 1; i++)
        f[u][i + 1] = f[f[u][i]][i];
    
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) continue;
        f[v][0] = u;
        dfs(v, u);
    }
}
int lca(int x, int y) {
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 20; i >= 0; i--)
        if (deep[f[x][i]] >= deep[y])
            x = f[x][i];
    //将要计算的两个节点先换到同一层
    //因为在换节点的时候，x一直在变，所有数字都可以拆成2的倍数之和（而且不重复），所以可以换到同一层
    if (x == y) return x;
    
    for (int i = 20; i >= 0; i--)
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    //将两个节点同时上移（同步移动），
    return f[x][0];
}
int dist(int u, int v) {
    return deep[u] + deep[v] - 2 * deep[lca(u, v)];
}
//函数区