倍增法

倍增法（binary lifting）是一种用于解决树上最近公共祖先（LCA）问题的算法。它的思路是预处理出每个节点的 $2^k$ 级祖先，然后通过不断跳跃到更深的祖先来找到两个节点的 LCA。

具体来说，倍增法的步骤如下：

1. 预处理每个节点的 $2^k$ 级祖先。具体来说，令 $fa_{i,j}$ 表示节点 $i$ 的 $2^j$ 级祖先，那么有：

fa_{i,j}=\\begin{cases} p,&\\text{if }j=0,\\\\ fa_{fa_{i,j-1},j-1},&\\text{if }j>0. \\end{cases}fai,j={p,fafai,j−1,j−1,if j=0,if j>0.

其中 $p$ 表示节点 $i$ 的父节点。

1. 对于两个节点 $u$ 和 $v$，设它们的深度分别为 $d_u$ 和 $d_v$，不失一般性，假设 $d_u\\geq d_v$。令 $k=\\lfloor \\log_2 (d_u-d_v)\\rfloor$，那么可以先将 $u$ 向上跳 $2^k$ 级，然后再将 $u$ 和 $v$ 分别向上跳 $2^k,2^{k-1},\\ldots,2^0$ 级，直到 $u$ 和 $v$ 的祖先相同或者达到根节点。

2. 最后，$u$ 和 $v$ 的公共祖先就是它们跳到的最深的相同祖先。

时间复杂度为 $O(n\\log n)$，其中 $n$ 是树的节点数。预处理需要 $O(n\\log n)$ 的时间，每次询问需要 $O(\\log n)$ 的时间。倍增法的优点是空间复杂度低，只需要 $O(n\\log n)$ 的空间，因为每个节点只需要存储 $O(\\log n)$ 个祖先。

除了解决 LCA 问题之外，倍增法还可以用于解决一些其他的树上问题，例如树上第 $k$ 大节点、树上最长路等。

下面给出一个应用倍增法求树上第 $k$ 大节点的例子。假设要求一棵树的第 $k$ 大节点，可以先对树进行一次 DFS，按照 DFS 序将树转化为一个序列。然后将该序列排序，第 $k$ 大节点就是序列中第 $k$ 个节点。这个做法的时间复杂度是 $O(n\\log n)$，其中 $n$ 是树的节点数，因为排序需要 $O(n\\log n)$ 的时间。

但是，如果 $k$ 很大，排序的时间复杂度会很高，因此可以考虑用倍增法来优化这个做法。具体来说，可以利用倍增法求出每个节点的 $2^k$ 大的子树，然后将每个子树中的节点按照 DFS 序加入一个大根堆。最后，从堆中取出第 $k$ 个节点即可。时间复杂度为 $O(n\\log n+\\min{k,n}\\log k)$。其中 $\\min{k,n}\\log k$ 表示堆的操作时间复杂度，因为堆的大小最多为 $k$。如果 $k$ 比较小，那么堆的时间复杂度就可以忽略不计，此时总时间复杂度为 $O(n\\log n)$。如果 $k$ 比较大，那么堆的时间复杂度就会成为主导因素，此时总时间复杂度为 $O(n\\log n+k\\log k)$。

下面是一个用 C++ 实现的求树上 LCA 的例子，采用倍增法：

const int N = 1e5 + 5, LOGN = 20;
vector<int> G[N];
int fa[N][LOGN], dep[N];

void dfs(int u, int p) {
    fa[u][0] = p;
    dep[u] = dep[p] + 1;
    for (int i = 1; i < LOGN; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int v : G[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    for (int i = LOGN - 1; i >= 0; i--) {
        if (dep[fa[u][i]] >= dep[v]) {
            u = fa[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = LOGN - 1; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << endl;
    }
    return 0;
}

其中，fa[u][i] 表示节点 u 的 $2^i$ 级祖先，dep[u] 表示节点 u 的深度。在 dfs 函数中，预处理出每个节点的 $2^k$ 级祖先和深度。在 lca 函数中，先将深度较大的节点向上跳，然后再一起向上跳，直到找到 LCA。

下面是一个用 C++ 实现的求树上第 $k$ 大节点的例子，采用倍增法和堆：

const int N = 1e5 + 5, LOGN = 20;
vector<int> G[N];
int fa[N][LOGN], dep[N], dfn[N], tot;

struct Node {
    int val, id;
    bool operator<(const Node &rhs) const {
        return val < rhs.val;
    }
};

void dfs(int u, int p) {
    fa[u][0] = p;
    dep[u] = dep[p] + 1;
    dfn[u] = ++tot;
    for (int i = 1; i < LOGN; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int v : G[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
}

int get_kth(int u, int k) {
    for (int i = LOGN - 1; i >= 0; i--) {
        int v = fa[u][i];
        if (dep[v] >= dep[u] - k) {
            u = v;
        }
    }
    return u;
}

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    priority_queue<Node> Q;
    for (int i = 1; i <= n; i++) {
        Q.push({dfn[i], i});
        if (Q.size() > k) {
            Q.pop();
        }
    }
    cout << Q.top().id << endl;
    return 0;
}

其中，dfn[u] 表示节点 u 在 DFS 序中的编号。在 dfs 函数中，预处理出每个节点的 $2^k$ 级祖先、深度和 DFS 序编号。在 get_kth 函数中，返回节点 u 的第 $k$ 个祖先。在主函数中，先将所有节点加入一个大根堆，然后依次弹出堆顶元素，直到堆的大小等于 $k$。最后，输出堆顶元素的节点编号。注意，由于堆的大小最多为 $k$，所以最终的时间复杂度为 $O(n\\log n+\\min{k,n}\\log k)$。如果 $k$ 比较小，那么堆的时间复杂度就可以忽略不计，此时总时间复杂度为 $O(n\\log n)$。如果 $k$ 比较大，那么堆的时间复杂度就会成为主导因素，此时总时间复杂度为 $O(n\\log n+k\\log k)$。