[3584] 가장 가까운 공통 조상

https://www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

루트만 찾아서 lca로 구했다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

constexpr int MAX = 14;

int n, p[10005][MAX], d[10005], dg[10005];

vector<int> adj[10005];

void dfs(int cur) {

    for (int nxt : adj[cur]) {

        if (d[nxt] != -1) continue;

        d[nxt] = d[cur] + 1;

        p[nxt][0] = cur;

        dfs(nxt);

    }

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    int t;

    cin >> t;

    while (t--) {

        int i, j;

        cin >> n;

        for (i = 1; i <= n; i++) adj[i].clear();

        memset(dg, 0, sizeof(dg));

        for (i = 0; i < n - 1; i++) {

            int a, b;

            cin >> a >> b;

            adj[a].push_back(b);

            adj[b].push_back(a);

            dg[b]++;

        }

        memset(p, -1, sizeof(p));

        memset(d, -1, sizeof(d));

        int root;

        for (i = 1; i <= n; i++) {

            if (dg[i] == 0) {

                root = i;

                break;

            }

        }

        d[root] = 0;

        dfs(root);

        for (j = 0; j < MAX - 1; j++)

            for (i = 1; i <= n; i++)

                if (p[i][j] != -1) p[i][j + 1] = p[p[i][j]][j];

        int a, b;

        cin >> a >> b;

        if (d[a] < d[b]) swap(a, b);

        int diff = d[a] - d[b];

        for (j = 0; diff; j++) {

            if (diff & 1) a = p[a][j];

            diff >>= 1;

        }

        if (a == b) {

            cout << a << '\n';

            continue;

        }

        for (j = MAX - 1; j >= 0; j--) {

            if (p[a][j] != -1 && p[a][j] != p[b][j]) {

                a = p[a][j];

                b = p[b][j];

            }

        }

        a = p[a][0];

        cout << a << '\n';

    }

    return 0;

}

---