1 条题解

  • 0
    @ 2025-6-5 13:03:31
    #include <bits/stdc++.h>
    using namespace std;
    int n,m,s;
    vector<int> adj[500000];
    
    int depth[500000];
    int parent[500000][20];
    
    void dfs(int u, int p) {
        depth[u] = depth[p] + 1;
        parent[u][0] = p;
        for (int i = 1; i <= 19; i++) {
            parent[u][i] = parent[parent[u][i - 1]][i - 1];
        }
        for (int i = 0;i < adj[u].size(); i++) {
            int v = adj[u][i];
            if (v == p) {
                continue;
            }
            dfs(v, u);
        }
    }
    
    int LCA(int x,int y) {
        if (depth[x] < depth[y]) {
            swap(x, y);
        }
    
        for (int i = 19; i >= 0; i--) {
            if (depth[parent[x][i]] >= depth[y]) {
                x = parent[x][i];
            }
        }
        if (x == y) {
            return x;
        }
        for (int i = 19; i >= 0; i--) {
            if (parent[x][i] != parent[y][i]) {
                x = parent[x][i];
                y = parent[y][i];
            }
        }
    
        return parent[x][0];
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    
        cin >> n >> m >> s;
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    
        dfs(s, 0);
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            cout << LCA(x, y) << '\n';
        }
    
    
        return 0;
    }
    
    
    
    • 1

    信息

    ID
    1965
    时间
    2000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    34
    已通过
    8
    上传者