# 11595: 【原1595】LCA

### 题目描述

author: Crystal 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1595

## Description

Crystal家有一棵树。树上有n个节点，编号由1到n（1号点是这棵树的根）。Crystal有Q个问题，每次询问编号为x的节点与编号为y的节点的最近公共祖先。

## Output Format

Q行，每行一个整数，表示对第i个询问的回答，输出节点x与节点y的最近公共祖先的编号。

## Sample Input

``````5 3
1 2
1 3
3 4
3 5
1 3
4 2
4 5
``````

## Sample Output

``````1
1
3
``````

## Limits

• 对于50%的数据，保证n <= 1000, Q <= 1000。
• 对于70%的数据，保证n <= 10000, Q <= 1000
• 对于100%的数据，保证n <= 100000, Q <= 100000;
• 对于100%的数据，保证所有输入数据均为非负整数，且在int范围内。

## yyong119's solution

``````#include <cstdio>
#include <vector>
#include <algorithm>
#define M 100011
using namespace std;

{
char ch; int ret = 0;
for (ch = getchar(); ch<'0' || ch>'9'; ch = getchar());
for (; ch >= '0'&& ch <= '9'; ret = ret * 10 + ch - '0', ch = getchar());
return ret;
}

vector<int> G[M];
int anc[18][M] = { 0 }, que[M], dep[M] = { 0 };
bool visit[M] = { 0 };

int find_LCA(int a, int b) {
if (a == b) return a;
for (int k = 17; k >= 0; --k) if (anc[k][a] != anc[k][b]) a = anc[k][a], b = anc[k][b];
return anc[0][a];
}

void maintain(int & a, int & b) {
if (dep[a] < dep[b]) swap(a, b);
for (int k = 17; k >= 0; --k) if (dep[anc[k][a]] >= dep[b]) a = anc[k][a];
//for (int d = dep[a] - dep[b], i = 0; d; d >>= 1, ++i) if (d & 1) a = anc[i][a];
}

int main() {

int n, q, x, y;
scanf("%d%d", &n, &q);
for (int i = 1; i < n; ++i) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
int front = 1, rear = 1;
que[1] = 1, dep[1] = 1, visit[1] = true;
while (front <= rear) {
x = que[front];
for (int i = 0; i < G[x].size(); ++i) {
if (visit[G[x][i]]) continue;
visit[G[x][i]] = true;
que[++rear] = G[x][i];
dep[G[x][i]] = dep[x] + 1;
anc[0][G[x][i]] = x;
for (int j = 1; j <= 17; ++j) {
anc[j][G[x][i]] = anc[j - 1][anc[j - 1][G[x][i]]];
}
}
++front;
}
for (int i = 1; i <= q; ++i) {