洛谷P3379
#include <iostream> #include <vector> #include <stack> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <cstring> #include <unordered_map> #include <unordered_set> #include <algorithm> #include <numeric> #include <chrono> #include <ctime> #include <cmath> #include <cctype> #include <string> #include <cstdio> #include <iomanip> #include <thread> #include <mutex> #include <condition_variable> #include <functional> #include <iterator> using namespace std; //链式前向星 const int MAXSIZE = 501000; struct Tail { int to, next; }tail[MAXSIZE << 1]; int head[MAXSIZE << 1 ] = { 0 }, f[MAXSIZE << 1 ][21] = { 0 }, dep[MAXSIZE << 1 ] = {0},tot = 0; //head数组 相当于 尾巴节点的头指针(第一个) //tail 是尾巴节点 next 指向 下一个尾巴 节点下标 void Add(int _head, int _tail) { //++tot 相当于 创建一个新节点, .to 记录尾巴节点 tail[++tot].to = _tail; //head[_head] 相当于 邻接表里面的头指针 , 将新节点的 next 指向 头指针 tail[tot].next = head[_head]; //将头指针指向 新节点 head[_head] = tot; } void dfs(int u,int fa) { dep[u] = dep[fa] + 1; f[u][0] = fa; for (int i = 1; i < 20; ++i) { f[u][i] = f[ f[u][i-1] ][ i-1 ]; } for (int i = head[u]; i; i = tail[i].next) { int v = tail[i].to; if (v == fa) continue; dfs(v, u); } } int LCA(int u, int v) { if (dep[u] > dep[v]) swap(u, v); //到同一层上 for (int i = 20; i >= 0; --i) { if (dep[u] + (1 << i) <= dep[v]) { v = f[v][i]; } } if (u == v) return u; for (int i = 20; i >= 0; --i) { if (f[u][i] != f[v][i]) { u = f[u][i]; v = f[v][i]; } } return f[u][0]; } int main() { int n,m,start,over,a,b,r; char ch; cin >> n >> m >> r; for (int i = 1; i < n; ++i) { cin >> start >> over; Add(start, over); Add(over, start); } dfs(r, 0); for (int i = 0; i < m; ++i) { cin >> a >> b; cout << LCA(a, b) << endl; } cout << endl; return 0; }