RMQ在线求LCA

#include<bits/stdc++.h> using namespace std; #define begin Begin #define next Next #define rank Rank #define REP(i, a, b) for (int i = (a), _end_ = (b); i <= _end_; ++i) #define ER(i, a) for (int i = begin[a]; i; i = next[i]) #define debug(...) fprintf(stderr, __VA_ARGS__) template<typename T> inline bool chkmin(T &a, const T &b){ return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b){ return a < b ? a = b, 1 : 0; } template<class T> inline T read() { T sum = 0, fg = 1, c = getchar(); while (c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); } while (c >= '0' && c <= '9') sum = sum * 10 + c - '0', c = getchar(); return sum * fg; } typedef long long LL; const int dmax = 300100, oo = 0x3f3f3f3f; int N, M; int begin[dmax], next[dmax], to[dmax], cnt = 0; void add(const int &x, const int &y, const int &type = 1) { to[++cnt] = y; next[cnt] = begin[x]; begin[x] = cnt; if (type) add(y, x, 0); } int lg[dmax]; int rank[dmax], dis[dmax], cur = 0, Dis = 0; int rmq[20][dmax]; void dfs(const int &x) { rank[x] = ++cur, rmq[0][cur] = x; ER(i, x) if (!rank[to[i]]) { dis[to[i]] = dis[x] + 1, dfs(to[i]); rmq[0][++cur] = x; } } inline int Min(const int &x, const int &y) { return dis[x] < dis[y] ? x : y; } inline void log_init() { REP(i, 1, cur) { lg[i] = log(i) / log(2); debug("%d\n", lg[i]); } } inline void rmq_init() { int N = cur; REP(i, 1, lg[N]) REP(j, 1, N - (1 << i) + 1) rmq[i][j] = Min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]); } inline int LCA(int x, int y) { x = rank[x], y = rank[y]; if (x > y) swap(x, y); int k = lg[y - x]; return Min(rmq[k][x], rmq[k][x + (1 << k) + 1]); } inline void init() { dis[1] = 1, dfs(1), log_init(), rmq_init(); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif N = read<int>(), M = read<int>(); REP(i, 1, N - 1) add(read<int>(), read<int>()); init(); while (M--) printf("%d\n", LCA(read<int>(), read<int>())); return 0; }