3.3节后习题

题目要求

一、基础题

1. 给定一棵完全二叉树，根为 1 号结点，求以下结点对的 LCA 和距离： (7, 8) (5, 9) (3, 6)

2. 证明：在完全二叉树中，结点 i 的父结点为 ⌊i/2⌋。

二、进阶题

1. 实现倍增法求解 LCA，以下哪个是倍增法的核心思想？

A使用DFS预处理每个节点的深度和父节点

B利用二进制拆分快速向上跳转找到LCA

C使用欧拉序将LCA问题转化为RMQ问题

D通过树链剖分优化LCA查询

2. 扩展代码支持计算树上任意两点距离，如何计算点u和点v的距离？

三、拓展题

1. 动态树场景下，若允许树的边权动态修改，下列哪种数据结构最适合优化距离计算？

A树链剖分 (HLD)

BLink-Cut Tree

C树状数组

DA和B都可以

2. 多结点LCA：计算三个结点u、v、w的LCA，最优算法是什么？

A分别计算两两结点的LCA再比较

B先计算lca(u,v)得到a，再计算lca(a,w)得到最终结果

C使用树链剖分一次性求出三点LCA

D使用Tarjan离线算法批量处理

---

参考代码

以下是倍增法求解LCA以及计算树上距离的参考代码：

代码

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

const int MAXN = 5e5 + 5;
const int LOG = 20;
vector<int> adj[MAXN];
int depth[MAXN];
int fa[MAXN][LOG];

void dfs(int u, int parent) {
    depth[u] = depth[parent] + 1;
    fa[u][0] = parent;
    for (int k = 1; k < LOG; k++)
        fa[u][k] = fa[fa[u][k-1]][k-1];
    for (int v : adj[u]) {
        if (v != parent)
            dfs(v, u);
    }
}

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

int get_distance(int u, int v) {
    int l = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[l];
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    depth[0] = -1;
    dfs(s, 0);
    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << endl;  // 求LCA
        // cout << get_distance(u, v) << endl;  // 求距离
    }
    return 0;
}