#include #include #include using namespace std; const int MAXN = 1e5 + 5; const int LOG = 20; // 2^20 > 1e5 vector adj[MAXN]; vector 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; }