作为一名金牌教练，我深知一套高质量的测试数据对训练的重要性。为了在 2MB 总量限制下（理想值）尽可能区分 $O(NM)$ 和 $O((N+M)\log N)$ 的复杂度，我们需要精心控制数据规模。

本生成器将生成 10 组测试点，涵盖了链状树（深抽）、星状树（浅宽）、随机树及小规模样例。为了防止爆栈，标程逻辑采用了 BFS 迭代版本。

数据生成器设计（C++14）

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <random>
#include <ctime>

using namespace std;

// --- 标程逻辑部分 (BFS 迭代版 LCA) ---
const int MAXLOG = 20;
vector<int> depth;
vector<vector<int>> fa;
vector<vector<int>> adj;

void build_lca(int n, int root) {
    depth.assign(n + 1, 0);
    fa.assign(n + 1, vector<int>(MAXLOG, 0));
    queue<int> q;

    depth[root] = 1;
    q.push(root);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!depth[v]) {
                depth[v] = depth[u] + 1;
                fa[v][0] = u;
                for (int k = 1; k < MAXLOG; k++)
                    fa[v][k] = fa[fa[v][k - 1]][k - 1];
                q.push(v);
            }
        }
    }
}

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

// --- 生成器逻辑部分 ---
void generate_test_point(int id, int n, int m, int type) {
    string in_file = to_string(id) + ".in";
    string out_file = to_string(id) + ".out";
    ofstream fout(in_file);
    ofstream fans(out_file);

    mt19937 rng(time(0) + id);
    int root = (rng() % n) + 1;
    fout << n << " " << m << " " << root << "\n";

    adj.assign(n + 1, vector<int>());
    vector<pair<int, int>> edges;

    if (type == 1) { // 链状树 (测试深度)
        vector<int> p(n);
        iota(p.begin(), p.end(), 1);
        shuffle(p.begin(), p.end(), rng);
        for (int i = 0; i < n - 1; i++) edges.push_back({p[i], p[i+1]});
    } else if (type == 2) { // 星状树 (测试宽度)
        for (int i = 1; i <= n; i++) if (i != root) edges.push_back({root, i});
    } else { // 随机树
        for (int i = 2; i <= n; i++) {
            int p = (rng() % (i - 1)) + 1; // 保证连接到已有的节点
            edges.push_back({i, p});
        }
    }

    for (auto& e : edges) {
        fout << e.first << " " << e.second << "\n";
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }

    build_lca(n, root);

    for (int i = 0; i < m; i++) {
        int u = (rng() % n) + 1;
        int v = (rng() % n) + 1;
        fout << u << " " << v << "\n";
        fans << query_lca(u, v) << "\n";
    }

    fout.close();
    fans.close();
    cout << "Test point " << id << " generated (N=" << n << ", M=" << m << ")" << endl;
}

int main() {
    // Case 1: 官方样例
    adj.assign(6, vector<int>());
    adj[3].push_back(1); adj[1].push_back(3);
    adj[2].push_back(4); adj[4].push_back(2);
    adj[5].push_back(1); adj[1].push_back(5);
    adj[1].push_back(4); adj[4].push_back(1);
    build_lca(5, 4);
    ofstream f1i("1.in"), f1o("1.out");
    f1i << "5 5 4\n3 1\n2 4\n5 1\n1 4\n2 4\n3 2\n3 5\n1 2\n4 5\n";
    f1o << query_lca(2,4) << "\n" << query_lca(3,2) << "\n" << query_lca(3,5) << "\n" << query_lca(1,2) << "\n" << query_lca(4,5) << "\n";
    f1i.close(); f1o.close();

    // Case 2: 极小边界 (N=2)
    generate_test_point(2, 2, 5, 0);

    // Case 3-4: 链状与星状 (中等规模)
    generate_test_point(3, 1000, 1000, 1);
    generate_test_point(4, 1000, 1000, 2);

    // Case 5-7: 混合结构 (能卡掉 O(NM))
    generate_test_point(5, 5000, 5000, 0);
    generate_test_point(6, 5000, 5000, 1);
    generate_test_point(7, 8000, 8000, 0);

    // Case 8-10: 较大规模 (控制文件大小在 2MB 以内)
    // 10^4 行数据约 150KB，总 10 个点约 1.5MB-2MB
    generate_test_point(8, 15000, 15000, 0);
    generate_test_point(9, 20000, 10000, 1);
    generate_test_point(10, 20000, 20000, 0);

    return 0;
}

数据设计与优化细节

1. 文件大小控制：

   • 在 NOI 官方测试中，$N, M$ 会给到 $5 \times 10^5$，但那会导致单个 .in 文件超过 10MB，不符合题目“理想值 2MB”的要求。
   • 本生成器将最大规模设为 $N, M = 20,000$。单组数据约 $40,000$ 行，每行平均 10 字节，约 400KB/组。10 组总计约 4MB，这是在保证能卡掉暴力算法的前提下做出的平衡。

2. 生成效率与剪枝：

   • 树生成逻辑优化：随机树采用 rng() % (i - 1) + 1 连边，这种方式天然保证了树的连通性和无环性，且生成复杂度为 $O(N)$。
   • 标程加速：使用 BFS 代替 DFS 预处理。在生成“链状树”时，DFS 会导致生成器自身爆栈（Stack Overflow），BFS 则非常安全。

3. 区分复杂度：

   • Case 3, 6, 9 (链状)：这是 $O(NM)$ 算法的噩梦，单次查询会退化到 $O(N)$。
   • Case 8, 10 (大规模)：由于询问量大，如果选手的 LCA 实现带有较大的常数或使用了 $O(N)$ 的搜索逻辑，将会明显超时。

4. 异常防御：

   • 所有节点编号从 1 开始，不存在除以 0 的情况。
   • 倍增数组 fa[v][k] 计算时采用了迭代方式，安全可靠。

使用方法：

1. 将代码保存为 gen.cpp 并使用 g++ -O3 gen.cpp -o gen 编译。
2. 运行程序，它将在当前文件夹下生成 1.in/1.out 到 10.in/10.out。
3. 将这些文件打包上传到 OJ（如 HUSTOJ, Hydro, Vijos 等）即可完成 LCA 模板题的配置。

在 NOI 竞赛中，LCA 问题是树论的基础。由于本题 $N, M$ 均达到 $5 \times 10^5$ 规模，算法的效率和常数至关重要。

以下是从暴力逐步优化到竞赛标准“倍增算法”的三个版本。

版本一：朴素爬坡法 (Naive Climbing) —— 暴力 （洛谷会TLE）

思路：

1. 通过 DFS 预处理每个节点的父节点 $p[u]$ 和深度 $depth[u]$。
2. 询问 $LCA(x, y)$ 时：
   • 先将深度较深的点（假设是 $x$）一步步向上爬到 $p[x]$，直到 $depth[x] == depth[y]$。
   • 然后 $x$ 和 $y$ 同时向上爬一步，直到相遇。

评价：

• 时间复杂度：预处理 $O(N)$，单次查询最坏 $O(N)$。总复杂度 $O(NM)$。
• 结果：在 $5 \times 10^5$ 规模下会严重超时（TLE），仅能通过 20% 左右的小规模数据。

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

const int MAXN = 500005;
vector<int> adj[MAXN];
int fa[MAXN], dep[MAXN];

// 预处理深度和父亲
void dfs(int u, int p, int d) {
    fa[u] = p;
    dep[u] = d;
    for (int v : adj[u]) {
        if (v != p) dfs(v, u, d + 1);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    // 1. 爬到同一深度
    while (dep[x] > dep[y]) x = fa[x];
    // 2. 同时爬，直到相遇
    while (x != y) {
        x = fa[x];
        y = fa[y];
    }
    return x;
}

int main() {
    int n, m, s;
    scanf("%d %d %d", &n, &m, &s);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(s, 0, 1);
    while (m--) {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}

版本二：标准倍增算法 (Binary Lifting) —— 竞赛标准

思路分析： 利用二进制拆分（快速幂思想）。

1. $fa[u][i]$ 表示 $u$ 向上跳 $2^i$ 步到达的祖先。
2. 转移方程：fa[u][i] = fa[fa[u][i-1]][i-1]（跳 $2^i$ 步等于跳两次 $2^{i-1}$ 步）。
3. 查询时，利用 $fa[u][i]$ 进行对数级跳跃。

时间复杂度分析：

• 预处理：$O(N \log N)$（填充二维数组）。
• 查询：每次 $O(\log N)$。
• 总复杂度：$O((N+M) \log N)$。对于 $5 \times 10^5$，约 $1.5 \times 10^7$ 次运算，在 1.0s 内可以过。

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 500005;
const int MAXLOG = 21; // 2^20 > 500,000

vector<int> adj[MAXN];
int fa[MAXN][MAXLOG], dep[MAXN];
int lg[MAXN]; // 预处理 log 数组，用于常数优化

void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u][0] = p;
    // 预处理倍增表
    for (int i = 1; i < MAXLOG; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int v : adj[u]) {
        if (v != p) dfs(v, u);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    // 1. 对齐深度：利用二进制拆分向上跳
    for (int i = MAXLOG - 1; i >= 0; i--) {
        if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    }
    if (x == y) return x;
    // 2. 倍增同步跳
    for (int i = MAXLOG - 1; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) { // 只要跳完不相等，说明还没跳到 LCA，可以跳
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0]; // 跳到 LCA 的下一层，返回其父节点
}

int main() {
    int n, m, s;
    if (scanf("%d %d %d", &n, &m, &s) != 3) return 0;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(s, 0);
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}

版本三：最优复杂度优化建议 (Iterative + Fast I/O)

在实际 NOI 赛场上，如果数据非常极端，我们需要注意：

1. 栈溢出：$N=5 \times 10^5$ 的深链会导致递归 DFS 爆系统栈。
2. 读入瓶颈：巨大的输入数据需要更快的读入。

优化方案：

• 使用 链式前向星 替代 vector 节省空间和时间。
• 使用 非递归 DFS（手动模拟栈）或 BFS 预处理。
• 预处理 lg[i] 数组：lg[i] = lg[i/2] + 1。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

// 快速读入：对于 10^6 级别的数据，getchar() 效率远高于 scanf
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

const int MAXN = 500005;
const int MAXLOG = 20;

// 链式前向星：更底层的存图方式
int head[MAXN], to[MAXN << 1], nxt[MAXN << 1], tot;
inline void add(int u, int v) {
    to[++tot] = v; nxt[tot] = head[u]; head[u] = tot;
}

int fa[MAXN][21], dep[MAXN], lg[MAXN];

// 非递归 DFS 预处理：防止爆栈
void precompute(int root) {
    stack<int> s;
    s.push(root);
    dep[root] = 1;
    
    while(!s.empty()){
        int u = s.top(); s.pop();
        for(int i = head[u]; i; i = nxt[i]){
            int v = to[i];
            if(!dep[v]){
                dep[v] = dep[u] + 1;
                fa[v][0] = u;
                for(int j = 1; j <= 20; j++)
                    fa[v][j] = fa[fa[v][j-1]][j-1];
                s.push(v);
            }
        }
    }
}

int main() {
    int n = read(), m = read(), s = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        add(u, v); add(v, u);
    }
    
    precompute(s);
    
    // 预处理 log 数组辅助跳跃
    for(int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;

    while (m--) {
        int x = read(), y = read();
        if (dep[x] < dep[y]) swap(x, y);
        while (dep[x] > dep[y]) 
            x = fa[x][lg[dep[x] - dep[y]]];
        if (x == y) { printf("%d\n", x); continue; }
        for (int k = 20; k >= 0; k--) {
            if (fa[x][k] != fa[y][k]) {
                x = fa[x][k]; y = fa[y][k];
            }
        }
        printf("%d\n", fa[x][0]);
    }
    return 0;
}

复杂度分析思考过程

1. 时间复杂度分析：

   • 存图：$O(N)$。
   • 预处理：每个节点走一次 $O(N)$，且每个节点更新一次倍增数组 $O(\log N)$。总计 $O(N \log N)$。
   • 查询：二进制拆分跳跃，每次 $O(\log N)$。
   • 结论：总时间 $O((N+M) \log N)$。

2. 空间复杂度分析：

   • fa[MAXN][21]：$5 \times 10^5 \times 21 \times 4$ 字节 $\approx 42$ MB。
   • head/to/nxt：$O(N)$。
   • 结论：总空间约 60-80 MB，远小于 NOI 256MB 或 512MB 的限制。

读题关键词总结与建议

• “有根树”：意味着节点关系明确，必须从根开始扩散。
• “无向边”：存储时必须双向加边 add(u, v), add(v, u)，否则无法遍历。
• “最近”：同步跳跃时判断 fa[x][k] != fa[y][k] 的逻辑确保了我们爬升到了 LCA 的直接子节点，这是该算法最巧妙的地方。
• “5e5”：暗示了 $O(NM)$ 必死，且提示需要处理递归栈和 I/O 效率。

建议： 在赛场上，优先写版本二。如果数据规模极大，再通过 read() 和非递归 DFS 提升鲁棒性。