题目分析与思路提示

1. 为什么暴力往上跳不行？

如果树是一条直线（链状），深度达到 $10^5$。每次查询最底下的两个点，需要跳 $10^5$ 步。总查询 $10^5$ 次，总运算量 $10^{10}$，严重超时。我们需要 $O(1)$ 或 $O(\log N)$ 的查询速度。

2. 核心算法：倍增法求 LCA

我们使用倍增 (Binary Lifting) 思想来进行预处理和查询。

关键定义：

• depth[u]：节点 $u$ 的深度（根为1）。
• up[u][i]：节点 $u$ 向父节点方向跳 $2^i$ 步到达的祖先节点。
  • up[u][0] 就是 $u$ 的父亲（跳 $2^0=1$ 步）。
  • up[u][1] 是爷爷（跳 $2^1=2$ 步）。
  • 递推公式：up[u][i] = up[up[u][i-1]][i-1]。
  • 原理：跳 $2^i$ 步 等于 先跳 $2^{i-1}$ 步，再从那里跳 $2^{i-1}$ 步。

查询流程 (Get LCA)： 假设我们要找 $u$ 和 $v$ 的 LCA：

1. 对齐深度：不妨设 depth[u] >= depth[v]。先把 $u$ 往上跳，直到 $u$ 和 $v$ 在同一深度。
   • 利用倍增数组，从大步 ($2^{19}$) 试到小步 ($2^0$)，能跳就跳。
2. 特判：如果此时 $u == v$，说明 $v$ 原本就是 $u$ 的祖先，LCA 就是 $v$。
3. 一起往上跳：让 $u$ 和 $v$ 同步往上跳，直到它们父亲相同的前一刻。
   • 从大到小枚举 $i$。如果 up[u][i] != up[v][i]（说明跳 $2^i$ 步还没相遇），那就跳上去：$u = up[u][i], v = up[v][i]$。
   • 如果相等，说明跳过了或正好是公共祖先，先不跳，保留悬念，尝试更小的步数。
4. 终局：循环结束后，$u$ 和 $v$ 一定只差一步就相遇了。此时 up[u][0] 就是 LCA。

3. 复杂度分析

• 预处理：遍历整棵树 $O(N)$，每个点计算约 20 个倍增祖先。总计 $O(N \log N)$。
• 查询：每次查询最多跳 $2 \times \log N$ 次。总计 $O(Q \log N)$。
• 总复杂度：$O((N+Q) \log N)$。
  • 代入 $N, Q = 10^5$，约 $3.4 \times 10^6$ 次运算，速度飞快。

参考代码 (C++14)

/**
 * 题目：苏氏族谱 (The Su Family Genealogy)
 * 难度：GESP 6级
 * 算法：LCA (倍增法)
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 100005;
const int LOGN = 20; // 2^19 > 100000，20层足够

// 邻接表存树
vector<int> adj[MAXN];

// up[u][i] 表示 u 向上跳 2^i 步的祖先
int up[MAXN][LOGN];
// depth[u] 表示 u 的深度
int depth[MAXN];

// DFS 预处理深度和父节点（倍增表的第一列）
// u: 当前节点, p: 父节点, d: 深度
void dfs(int u, int p, int d) {
    depth[u] = d;
    up[u][0] = p; // 跳 2^0 = 1 步就是父节点

    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u, d + 1);
        }
    }
}

// 预处理倍增表
void init_lca(int n) {
    // 根节点的父亲设为自己或0，防止越界
    // 在 dfs 中 up[1][0] 被设为 0 (如果调用 dfs(1, 0, 1))
    
    for (int j = 1; j < LOGN; ++j) {
        for (int i = 1; i <= n; ++i) {
            // 如果 2^(j-1) 步的祖先存在，则可以继续跳
            if (up[i][j - 1] != 0) {
                up[i][j] = up[up[i][j - 1]][j - 1];
            } else {
                up[i][j] = 0; // 超过根节点了，记为0
            }
        }
    }
}

// 查询 LCA
int get_lca(int u, int v) {
    // 1. 确保 u 是深度较深的那个
    if (depth[u] < depth[v]) swap(u, v);

    // 2. 将 u 向上跳，直到和 v 同深度
    // 从大步尝试到小步
    for (int j = LOGN - 1; j >= 0; --j) {
        // 如果跳完之后深度依然 >= v 的深度，就跳
        // up[u][j] != 0 保证不出界
        if (depth[u] - (1 << j) >= depth[v]) {
            u = up[u][j];
        }
    }

    // 3. 如果此时重合，v 就是 LCA
    if (u == v) return u;

    // 4. 两个点同时向上跳，直到父亲相同的前一步
    for (int j = LOGN - 1; j >= 0; --j) {
        // 如果跳 2^j 步后不一样，说明还没相遇，赶紧跳上去
        if (up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
    }

    // 此时 u 和 v 的父节点就是 LCA
    return up[u][0];
}

int main() {
    fast_io();

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    // 读入树
    // 注意：题目给的是 x 是 y 的父亲，是有向关系，但为了通用性常存无向图+DFS判重
    // 或者直接存有向图 adj[x].push_back(y)
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); // u 是 v 的父亲
        // adj[v].push_back(u); // 如果输入没保证父子顺序，需要建无向图
    }

    // 预处理
    // 根节点是 1，父亲设为 0，深度设为 1
    dfs(1, 0, 1);
    init_lca(N);

    // 处理询问
    for (int i = 0; i < Q; ++i) {
        int u, v;
        cin >> u >> v;
        cout << get_lca(u, v) << "\n";
    }

    return 0;
}

数据生成器 (Data Generator)

用于生成 1.in ~ 10.in 及其标准答案。特别注意生成防止爆栈的链状数据和一般的随机树。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out) - 防爆栈版
// ------------------------------------------
const int MAXN = 100005;
const int LOGN = 20;
vector<int> g_adj[MAXN];
int g_up[MAXN][LOGN];
int g_depth[MAXN];

// 使用 BFS 预处理，防止链状树爆栈
void bfs_preprocess(int root, int n) {
    for(int i=1; i<=n; i++) g_depth[i] = 0;
    
    queue<int> q;
    q.push(root);
    g_depth[root] = 1;
    g_up[root][0] = 0; // root parent is 0

    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v : g_adj[u]){
            if(g_depth[v] == 0) { // unvisited
                g_depth[v] = g_depth[u] + 1;
                g_up[v][0] = u;
                q.push(v);
            }
        }
    }

    // 倍增
    for(int j=1; j<LOGN; j++) {
        for(int i=1; i<=n; i++) {
            if(g_up[i][j-1] != 0) g_up[i][j] = g_up[g_up[i][j-1]][j-1];
            else g_up[i][j] = 0;
        }
    }
}

int get_lca_solve(int u, int v) {
    if(g_depth[u] < g_depth[v]) swap(u, v);
    for(int j=LOGN-1; j>=0; j--) {
        if(g_depth[u] - (1<<j) >= g_depth[v]) u = g_up[u][j];
    }
    if(u == v) return u;
    for(int j=LOGN-1; j>=0; j--) {
        if(g_up[u][j] != g_up[v][j]) {
            u = g_up[u][j];
            v = g_up[v][j];
        }
    }
    return g_up[u][0];
}

void solve(int N, int Q, const vector<pair<int, int>>& edges, const vector<pair<int, int>>& queries, ofstream& fout) {
    for(int i=1; i<=N; i++) g_adj[i].clear();
    for(auto& e : edges) g_adj[e.first].push_back(e.second); // 父->子

    bfs_preprocess(1, N);

    for(auto& q : queries) {
        fout << get_lca_solve(q.first, q.second) << "\n";
    }
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, Q;
        vector<pair<int, int>> edges;
        vector<pair<int, int>> queries;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 5; Q = 3;
            edges = {{1,2}, {1,3}, {2,4}, {2,5}};
            queries = {{4,5}, {3,4}, {4,2}};
        }
        else if (i == 2) {
            // 链状 (1->2->...->N)
            N = 100; Q = 50;
            for(int k=1; k<N; k++) edges.push_back({k, k+1});
            for(int k=0; k<Q; k++) queries.push_back({randRange(1, N), randRange(1, N)});
        }
        else if (i == 3) {
            // 菊花图 (1连所有)
            N = 100; Q = 50;
            for(int k=2; k<=N; k++) edges.push_back({1, k});
            for(int k=0; k<Q; k++) queries.push_back({randRange(2, N), randRange(2, N)});
        }
        else if (i == 4) {
            // 二叉树结构
            N = 1000; Q = 1000;
            for(int k=2; k<=N; k++) edges.push_back({k/2, k});
            for(int k=0; k<Q; k++) queries.push_back({randRange(1, N), randRange(1, N)});
        }
        else if (i == 5) {
            // LCA 是自身的测试
            N = 1000; Q = 1000;
            for(int k=2; k<=N; k++) edges.push_back({randRange(1, k-1), k});
            // 构造必定有一点是另一点祖先的查询
            for(int k=0; k<Q; k++) {
                int u = randRange(1, N);
                // 简单地让 v = u 也是一种情况，或者 v=1
                queries.push_back({1, u}); 
            }
        }
        else if (i == 6) {
            // 极端链状 (N=10^5) 测试爆栈和效率
            N = 100000; Q = 10000;
            for(int k=1; k<N; k++) edges.push_back({k, k+1});
            for(int k=0; k<Q; k++) queries.push_back({randRange(1, N), randRange(1, N)});
        }
        else {
            // 大规模随机 (N=10^5)
            N = 100000; Q = 100000;
            // 随机树生成策略：点 i 随机挂在 1~i-1 下面
            for(int k=2; k<=N; k++) {
                int p = randRange(max(1, k-200), k-1); // 稍微限制父节点范围，增加树高
                edges.push_back({p, k});
            }
            for(int k=0; k<Q; k++) queries.push_back({randRange(1, N), randRange(1, N)});
        }

        // 写入输入
        fin << N << " " << Q << "\n";
        for(auto& e : edges) fin << e.first << " " << e.second << "\n";
        for(auto& q : queries) fin << q.first << " " << q.second << "\n";

        // 写入输出
        solve(N, Q, edges, queries, fout);

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}