树上倍增

模板：1483. 树节点的第 K 个祖先 - 力扣（LeetCode）

pa[i] [j]表示节点i的第2^j个祖先，时刻牢记外层循环为j，内层循环为i。

LCA问题：

预处理得到pa数组，pa[i] [j]表示节点i的第2^j个祖先;

求解x和y的最近公共祖先时，首先较深的节点(假设为y)转为与x相同的深度上，即y = getKthAncestor(depth[y] - depth[x])，如果此时x == y，那么x即为结果。

否则二者同步向上找，从节点数n的最高位开始遍历：

  • 若pa[x] [i] == -1 || pa[x] [i] == pa[y] [i]，说明步子迈大了，继续循环
  • 若pa[x] [i] != -1 && pa[x] [i] != pa[y] [i]，说明lca还在上方，将x更新为 pa[x] [i] , y更新为 pa[y] [i]，将i减1继续循环。

上述做法能跳就尽量跳，不会错过任何可以上跳的机会。所以循环结束时，lca与x仅一步之遥。即lca = pa[x] [0]。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class TreeAncestor {
    private int[] depth;
    private int[][] pa;

    public TreeAncestor(int[][] edges) {
        int n = edges.length + 1;
        int m = 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度
        List<Integer> g[] = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) { // 节点编号从 0 开始
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }

        depth = new int[n];
        pa = new int[n][m];
        dfs(g, 0, -1);

        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                int p = pa[x][i];
                pa[x][i + 1] = p < 0 ? -1 : pa[p][i];
            }
        }
    }

    private void dfs(List<Integer>[] g, int x, int fa) {
        pa[x][0] = fa;
        for (int y : g[x]) {
            if (y != fa) {
                depth[y] = depth[x] + 1;
                dfs(g, y, x);
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        for (; k > 0; k &= k - 1)
            node = pa[node][Integer.numberOfTrailingZeros(k)];
        return node;
    }

    public int getLCA(int x, int y) {
        if (depth[x] > depth[y]) {
            int tmp = y;
            y = x;
            x = tmp;
        }
        // 使 y 和 x 在同一深度
        y = getKthAncestor(y, depth[y] - depth[x]);
        if (y == x)
            return x;
        for (int i = pa[x].length - 1; i >= 0; i--) {
            int px = pa[x][i], py = pa[y][i];
            if (px != py) {
                x = px;
                y = py;
            }
        }
        return pa[x][0];
    }
}

时间复杂度：初始化O(NlogN), getLCA单次执行O(logN)

空间复杂度:O(NlogN)

题目：2846. 边权重均等查询 - 力扣（LeetCode）

Tarjan

基于树上倍增的算法求LCA可以做到在线查询，但单次get的时间复杂度是O(logN)的。Tarjan算法可以线性复杂度、离线地求LCA，也就是说，需要一次性传入所有查询。
与求强连通分量、割点割边时不同，此时的Tarjan不需要保存访问到某个节点的时间戳，只需要用一个color数组表示该节点的递归过程即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class TreeAncester {
    int[] color, root, ret;
    List<Integer>[] g;
    List<int[]>[] qs;

    TreeAncester(int n, int[][] edges){
        this.g = new List[n];   // 建图
        this.qs = new List[n];  // 保存所有查询，包括其在查询数组中的下标
        this.root = new int[n]; // 并查集的簇头节点
        this.color = new int[n];    // Tarjan过程中的染色数组
        Arrays.setAll(g, k->new ArrayList<>());
        Arrays.setAll(qs, k->new ArrayList<>());
        for(int i = 1;i < n;++i) root[i] = i;
        for(int[] edge: edges) {
            int u = edge[0], v = edge[1];
            g[u].add(v);
            g[v].add(u);
        }
    }

    public void Tarjan(int cur, int fa){
        color[cur] = 1; // 正在递归
        for(int nxt: g[cur]){
            if(color[nxt] != 0) continue;
            // 这两句不能调换顺序，否则所有lca都会变成tarjan的入口节点
            Tarjan(nxt, cur);
            root[nxt] = cur;    // 相当于把 nxt 的子树节点全部 merge 到 cur
        }
        for(int[] q: qs[cur]){
            // color[y] == 2 意味着 y 所在子树已经遍历完
            // 也就意味着 y 已经 merge 到它和 x 的 lca 上了
            // 此时 find(y) 就是 x 和 y 的 lca
            int node = q[0], idx = q[1];
            if(node == cur || color[node] == 2){
                int lca = find(node);
                ret[idx] = lca;
            }
        }
        color[cur] = 2; // 递归结束
    }

    // 并查集查找簇头
    public int find(int x){
        return root[x] == x ? x : (root[x] = find(root[x]));
    }

    // 离线传入所有的查询，返回结果
    public int[] getLCAs(int[][] querys){
        int m = querys.length;
        this.ret = new int[m];
        for(int i = 0;i < m;++i){
            int[] query = querys[i];
            int u = query[0], v = query[1];
            qs[u].add(new int[]{v, i});
            if(u != v) qs[v].add(new int[]{u, i});
        }
        Tarjan(0, -1);  // 从根节点开始Tarjan
        return ret;
    }
}

复杂度O(n+mα)，其中α为反阿克曼函数，可以认为是O(1)

题目：2646. 最小化旅行的价格总和 - 力扣（LeetCode）

__END__