Skip to content

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的节点的最近公共祖先。

Input Format

第1行两个整数n,Q,分别表示树上有n个点和Crystal有Q个问题。

接下来的n - 1行,每行两个整数u,v,表示编号为u的点与编号为v的点直接相连。

接下来Q行,每行两个整数x,y,表示编号为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;

inline int read()
{
    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 = read(), q = read(), x, y;
    int n, q, x, y;
    scanf("%d%d", &n, &q);
    for (int i = 1; i < n; ++i) {
        //x = read(), y = read();
        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) {
        //x = read(), y = read();
        scanf("%d%d", &x, &y);
        if (dep[x] != dep[y]) maintain(x, y);
        printf("%d\n", find_LCA(x, y));
    }
    return 0;
}