//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "最近公共祖先": {
        "prefix": "acm-4.1lca",
        "body": [
            "#include <iostream>",
            "#include <vector>",
            "#include <queue>",
            "using namespace std;",
            "",
            "const int MAXN = 1e5 + 5;",
            "const int LOG = 20;  // 2^20 > 1e5",
            "",
            "vector<int> adj[MAXN];",
            "vector<int> ch[MAXN];",
            "int depth[MAXN];",
            "int parent[MAXN][LOG];",
            "int n, m, root;",
            "",
            "// 预处理：计算每个节点的深度和2^k级祖先",
            "void dfs(int u, int p) {",
            "    depth[u] = depth[p] + 1;",
            "    parent[u][0] = p;",
            "    for (int k = 1; k < LOG; ++k) {",
            "        parent[u][k] = parent[parent[u][k-1]][k-1];",
            "    }",
            "    for (int v : adj[u]) {",
            "        if (v != p) {",
            "            ch[u].push_back(v);",
            "            dfs(v, u);",
            "        }",
            "    }",
            "}",
            "",
            "// 查找u和v的最近公共祖先",
            "int lca(int u, int v) {",
            "    if (depth[u] < depth[v]) {",
            "        swap(u, v);",
            "    }",
            "    // 将u提到与v同一深度",
            "    for (int k = LOG - 1; k >= 0; --k) {",
            "        if (depth[u] - (1 << k) >= depth[v]) {",
            "            u = parent[u][k];",
            "        }",
            "    }",
            "    if (u == v) {",
            "        return u;",
            "    }",
            "    // 同时向上跳",
            "    for (int k = LOG - 1; k >= 0; --k) {",
            "        if (parent[u][k] != parent[v][k]) {",
            "            u = parent[u][k];",
            "            v = parent[v][k];",
            "        }",
            "    }",
            "    return parent[u][0];",
            "}",
            "",
            "int main() {",
            "    ios::sync_with_stdio(false);",
            "    cin.tie(nullptr);",
            "",
            "    cin >> n >> m;",
            "    root = 1;",
            "    for (int i = 1; i < n; ++i) {",
            "        int u, v;",
            "        cin >> u >> v;",
            "        adj[u].push_back(v);",
            "        adj[v].push_back(u);",
            "    }",
            "",
            "    // 预处理",
            "    dfs(root, 0);",
            "",
            "    // lca查询",
            "    // cout << lca(u, v);",
            "    return 0;",
            "}"
        ],
        "description": "插入 最近公共祖先"
    }
}