• 一棵NN个节点的树，节点编号从00到N−1N-1
  • 每条边有为cc的边权
  • 求从两个不同的叶节点移动到同一节点最少花费
  • 共MM次询问

思路

如果只有一次询问，可以用最短路算法，然而询问次数过多，使用堆优化迪杰斯特拉在极限数据下计算次数将会达到101010^{10}级别

因为这是一棵树，所以我们可以很容易想到让两个叶子节点在同一高度向上跳，第一次同时跳到的点，维护两个节点跳过的距离就是最小花费

基于这种想法，我们成功引出了LCA——最近公共祖先

做法

求LCA

  • 倍增
  • ST表
  • Tarjan
  • 树链剖分 针对我现在是一个NOIP选手的现实基础，我选择使用简单好写的倍增求解法。

倍增求解

朴素算法

朴素LCA算法是先让更深的节点向上跳，跳到和深度较浅的点深度相同时，让两个节点同时向上跳，那么第一个跳到的同一个节点就是这两个节点的最近公共祖先。

可是这样太慢了，极限情况遇到一条链的树就会变成O(N)O(N)。

如何优化？

既然一次跳一步太少了，那就一次多跳几步

有一个神奇的东西叫做二进制拆分，就是可以把一个数拆成若干个2k2^k加和的形式，这样每个不大于它的正整数都可以用多项式中若干项的和来表示。

所以，我们用二元组f(i,j)f(i,j)表示从编号为ii的节点向上跳2j2^j步可以跳到的节点编号，用g(i,j)g(i,j)表示从编号为ii的节点向上跳2j2^j步所需花费（即边权和）。

那么对于每一个f(i,j)f(i,j)与g(i,j)g(i,j)，有

f(i,j)=f(f(i,j−1),j−1) f(i,j)=f(f(i,j-1),j-1) g(i,j)=g(i,j−1)+g(f(i,j−1),j−1) g(i,j)=g(i,j-1)+g(f(i,j-1),j-1)

这里用到了倍增的思想，就是从第ii个点往上跳2j2^j步相当于从第ii个点往上跳两个2j−12^{j-1}次方步，即先从ii向上跳2j2^j步，再从跳到的点向上跳2j2^j步。

BFS预处理

前面提到了一个操作，就是让两个点先到达同一深度，所以说我们需要用BFS预处理出深度。

设根节点深度为11，然后一层一层向下广搜，每次广搜出的点的深度为当前深度加一。

查询

qwq先上代码好了

inline int query (int u, int v) {
    if (N[u].depth < N[v].depth) std::swap(u, v); //保证u是较深的节点
    int ans = 0;
    if (N[u].depth > N[v].depth) {//使两个节点处在相同深度
        for (int j = logn; j >= 0; j--) { 
            if (N[f[u][j]].depth >= N[v].depth) {
                ans += g[u][j];
                u = f[u][j];
            }
        }//从大到小枚举指数，保证对应二进制位正常不进位
    } 
    if (u != v) {
        for (int j = logn; j >= 0; j--) {//同时向上跳
            if (f[u][j] != f[v][j]) {
                ans += g[u][j];
                ans += g[v][j];
                u = f[u][j];
                v = f[v][j];
            }//让两个节点跳到LCA的儿子
        }
        ans += g[u][0];
        ans += g[v][0];
        u = f[u][0];
    }
    return ans;//本题需要维护路径和
}

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
const int MAXN = 50000;
const int MAXLOG = 16;
int n, m, logn;
int f[MAXN + 5][MAXLOG];
int g[MAXN + 5][MAXLOG];
struct Node;
struct Edge;
struct Node {
    int depth;
    Edge *h;
    Node () :depth(0), h(NULL) {}
} N[MAXN];
struct Edge {
    Node *fr, *to;
    int w;
    Edge *ne;
    Edge (Node *fr, Node *to, int w) : fr(fr), to(to), w(w) {
        ne = fr->h;
    }
};
inline void addEdge (Node *u, Node *v, int w) {
    u->h = new Edge(u, v, w);
    v->h = new Edge(v, u, w);
} //用于BFS的邻接表
inline void bfs () {
    std::queue <Node *> q;
    q.push(&N[0]);
    N[0].depth = 1;
    f[0][0] = 0;
    g[0][0] = 0;
    while (!q.empty()) {
        Node *u = q.front();
        q.pop();
        for (Edge *e = u->h; e != NULL; e = e->ne) {
            if (!e->to->depth) {
                e->to->depth = u->depth + 1;
                f[e->to - N][0] = u - N;
                g[e->to - N][0] = e->w;
                q.push(e->to);
            }
        }
    }
}
inline void prepare () {
    bfs();
    while ((1 << logn) <= n) logn++;
    logn--;
    for (int j = 1; j <= logn; j++) {
        for (int i = 0; i < n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
            g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];
        }
    }
} //预处理出f,j数组
inline int query (int u, int v) {
    if (N[u].depth < N[v].depth) std::swap(u, v);
    int ans = 0;
    if (N[u].depth > N[v].depth) {
        for (int j = logn; j >= 0; j--) {
            if (N[f[u][j]].depth >= N[v].depth) {
                ans += g[u][j];
                u = f[u][j];
            }
        }
    }
    if (u != v) {
        for (int j = logn; j >= 0; j--) {
            if (f[u][j] != f[v][j]) {
                ans += g[u][j];
                ans += g[v][j];
                u = f[u][j];
                v = f[v][j];
            }
        }
        ans += g[u][0];
        ans += g[v][0];
        u = f[u][0];
    }
    return ans;
}
int main () {
    int m;
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addEdge(&N[u], &N[v], w);
        addEdge(&N[v], &N[u], w);
    }
    prepare();
    scanf("%d", &m);
    while (m--) {
        int u, v;
        scanf("%d %d", &u, &v);
        printf("%d\n", query(u, v));
    }
    return 0;
}

为什么说倍增好写又好用呢？因为Tarjan和ST表不能维护瓶颈路径（比如最大边或最小边），而树链剖分又比较难，所以贴心的队长就只讲了倍增qwq。