\uc8fc\uc5b4\uc9c4 N\uac1c\uc758 \ub178\ub4dc\uc640 N-1\uac1c\uc758 \uac04\uc120\uc73c\ub85c \uc774\ub8e8\uc5b4\uc9c4 \ud2b8\ub9ac\uac00 \uc788\uc2b5\ub2c8\ub2e4. \uac01 \ub178\ub4dc\ub294 1\ubd80\ud130 N\uae4c\uc9c0\uc758 \uc815\uc218\ub85c \ubc88\ud638\uac00 \ub9e4\uaca8\uc838 \uc788\uc2b5\ub2c8\ub2e4. \ub450 \uac1c\uc758 \ub178\ub4dc A\uc640 B\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \uc774 \ub450 \ub178\ub4dc\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1(LCA, Lowest Common Ancestor)\uc744 \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ub2e8, \uc774 \ubb38\uc81c\ub294 \ud2b8\ub9ac\uac00 \ub9e4\uc6b0 \ud074 \uc218 \uc788\uae30 \ub54c\ubb38\uc5d0, \ud6a8\uc728\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc744 \uc774\uc6a9\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
\n7\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n4 5\n3\n4 5\n4 6\n5 6\n<\/pre>\n\uc608\uc81c \ucd9c\ub825<\/h2>\n
\n2\n1\n3\n<\/pre>\n\ud574\uacb0 \uc804\ub7b5<\/h2>\n
\ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \ucc3e\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uc811\uadfc \ubc29\uc2dd\uc744 \uc0ac\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4.<\/p>\n
\n
- \ud2b8\ub9ac \uad6c\uc870\uc758 \ud45c\ud604:<\/strong> \ud2b8\ub9ac\ub294 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud45c\ud604\ub429\ub2c8\ub2e4. \uac01 \ub178\ub4dc\ub294 \ubd80\ubaa8\uc640 \uc790\uc2dd\uc73c\ub85c \uc5f0\uacb0\ub418\uc5b4 \uc788\uc73c\ubbc0\ub85c, \uc774\ub97c \ubc14\ud0d5\uc73c\ub85c \ud2b8\ub9ac\ub97c \uad6c\uc131\ud569\ub2c8\ub2e4.<\/li>\n
- DFS\ub97c \ud1b5\ud55c \uae4a\uc774 \ubc30\uc5f4\uacfc \ubd80\ubaa8 \ubc30\uc5f4 \uc0dd\uc131:<\/strong> DFS(Depth First Search) \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \uac01 \ub178\ub4dc\uc758 \uae4a\uc774\ub97c \uad6c\ud558\uace0, \ubd80\ubaa8 \ub178\ub4dc\ub97c \uae30\ub85d\ud569\ub2c8\ub2e4. \uc774 \uc815\ubcf4\ub294 LCA\ub97c \ucc3e\ub294 \ub370 \ud544\uc218\uc801\uc785\ub2c8\ub2e4.<\/li>\n
- \uc774\uc9c4 \uc81c\uc548\ubc95:<\/strong> LCA\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ucc3e\uae30 \uc704\ud574 \uc774\uc9c4 \uc81c\uc548\ubc95(Fast LCA)\uc744 \uc0ac\uc6a9\ud569\ub2c8\ub2e4. \ub450 \ub178\ub4dc\uc758 \uae4a\uc774\ub97c \ub9de\ucd94\uace0, \uac19\uc740 \uc870\uc0c1\uc744 \ucc3e\ub294 \ubc29\uc2dd\uc73c\ub85c \uc9c4\ud589\ub429\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\uad6c\ud604 \ub2e8\uacc4<\/h2>\n
1. \ud2b8\ub9ac \uad6c\uc870 \ub9cc\ub4e4\uae30<\/h3>\n
\uba3c\uc800 \uac04\uc120 \uc815\ubcf4\ub97c \ubc14\ud0d5\uc73c\ub85c \ud2b8\ub9ac\ub97c \uad6c\ucd95\ud569\ub2c8\ub2e4. \uc774 \uacfc\uc815\uc5d0\uc11c\ub294 \ubd80\ubaa8\uc640 \uc790\uc2dd \uac04\uc758 \uad00\uacc4\ub97c \uc815\uc758\ud558\uba70, \uc774\ub97c \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \ud1b5\ud574 \ud45c\ud604\ud569\ub2c8\ub2e4.<\/p>\n
2. DFS\ub85c \uae4a\uc774 \ubc0f \ubd80\ubaa8 \ubc30\uc5f4 \uc0dd\uc131\ud558\uae30<\/h3>\n
\uc774\uc81c DFS\ub97c \uc0ac\uc6a9\ud558\uc5ec \uac01 \ub178\ub4dc\uc758 \uae4a\uc774\uc640 \ubd80\ubaa8\ub97c \uae30\ub85d\ud574\uc57c \ud569\ub2c8\ub2e4. \uae4a\uc774\ub294 \uac01 \ub178\ub4dc\uac00 \ub8e8\ud2b8\uc5d0\uc11c \uc5bc\ub9c8\ub098 \ub5a8\uc5b4\uc838 \uc788\ub294\uc9c0\ub97c \ub098\ud0c0\ub0b4\uace0, \ubd80\ubaa8\ub294 \ub2e4\uc74c \ub2e8\uacc4\uc5d0\uc11c LCA\ub97c \ucc3e\ub294 \ub370 \ud544\uc218\uc801\uc785\ub2c8\ub2e4.<\/p>\n
3. LCA \ud568\uc218 \uad6c\ud604\ud558\uae30<\/h3>\n
\uc774\uc9c4 \uc81c\uc548\ubc95\uc744 \uc0ac\uc6a9\ud558\uc5ec \ub450 \ub178\ub4dc\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\ub294 \ud568\uc218\ub97c \uad6c\ud604\ud569\ub2c8\ub2e4. \uc774 \ud568\uc218\ub294 \ub450 \ub178\ub4dc\uc758 \uae4a\uc774\ub97c \ube44\uad50\ud558\uace0, \ud544\uc694\uc5d0 \ub530\ub77c \uae4a\uc774\ub97c \ub9de\ucd98 \ud6c4 \uc870\uc0c1\uc744 \ucc3e\uc544\uac00\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4.<\/p>\n
4. \ucffc\ub9ac \ucc98\ub9ac\ud558\uae30<\/h3>\n
\ucffc\ub9ac\uc5d0\uc11c \uc8fc\uc5b4\uc9c4 \ub450 \ub178\ub4dc A\uc640 B\uc5d0 \ub300\ud574 LCA\ub97c \ucc3e\uc544 \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n
\ucf54\ub4dc \uad6c\ud604<\/h2>\n
\n#include\n#include \n#include \n#include \n\nusing namespace std;\n\nconst int MAX_N = 100000;\nconst int LOG = 17; \/\/ log2(100000) \u2248 16.61\n\nint parent[MAX_N + 1][LOG + 1]; \/\/ \ubd80\ubaa8 \ubc30\uc5f4\nint depth[MAX_N + 1]; \/\/ \uae4a\uc774 \ubc30\uc5f4\nvector tree[MAX_N + 1]; \/\/ \uc778\uc811 \ub9ac\uc2a4\ud2b8 \ud615\uc2dd\uc758 \ud2b8\ub9ac\nint N;\n\nvoid dfs(int node, int par, int d) {\n depth[node] = d;\n parent[node][0] = par;\n for (int i = 1; i <= LOG; i++) {\n parent[node][i] = parent[parent[node][i - 1]][i - 1];\n }\n \n for (int child : tree[node]) {\n if (child != par) {\n dfs(child, node, d + 1);\n }\n }\n}\n\nint lca(int a, int b) {\n if (depth[a] < depth[b]) swap(a, b);\n\n for (int i = LOG; i >= 0; i--) {\n if (depth[parent[a][i]] >= depth[b]) {\n a = parent[a][i];\n }\n }\n\n if (a == b) return a;\n\n for (int i = LOG; i >= 0; i--) {\n if (parent[a][i] != parent[b][i]) {\n a = parent[a][i];\n b = parent[b][i];\n }\n }\n\n return parent[a][0];\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n\n cin >> N;\n for (int i = 0; i < N - 1; i++) {\n int u, v;\n cin >> u >> v;\n tree[u].push_back(v);\n tree[v].push_back(u);\n }\n\n dfs(1, 0, 0); \/\/ \ub8e8\ud2b8\ub294 1\n int Q;\n cin >> Q;\n\n for (int i = 0; i < Q; i++) {\n int a, b;\n cin >> a >> b;\n cout << lca(a, b) << '\\n';\n }\n\n return 0;\n}\n<\/int><\/cmath><\/algorithm><\/vector><\/iostream><\/pre>\n \ub9c8\ubb34\ub9ac<\/h2>\n
\uc774 \ubb38\uc81c\ub294 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\uae30 \uc704\ud574 DFS\uc640 \uc774\uc9c4 \uc81c\uc548\ubc95\uc744 \uc0ac\uc6a9\ud558\ub294 \ubc29\ubc95\uc744 \uc798 \uc774\ud574\ud558\ub294 \ub370 \ub3c4\uc6c0\uc744 \uc90d\ub2c8\ub2e4. \ud2b8\ub9ac\ub97c \ucc98\ub9ac\ud558\ub294 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \uc775\ud788\uace0, \ud6a8\uc728\uc801\uc778 \ucf54\ub529 \ub2a5\ub825\uc744 \uae30\ub974\ub294 \ub370 \ud070 \ub3c4\uc6c0\uc774 \ub420 \uac83\uc785\ub2c8\ub2e4. \uc8fc\uc5b4\uc9c4 \ubb38\uc81c\ub97c \uae30\ubc18\uc73c\ub85c \ub2e4\uc591\ud55c \ubc29\uc2dd\uc73c\ub85c \ud2b8\ub9ac \uad6c\uc870\ub97c \ud0d0\uc0c9\ud558\uace0 LCA\ub97c \ucc3e\ub294 \ubc29\ubc95\uc744 \uc5f0\uc2b5\ud558\uba74, \ucf54\ub529\ud14c\uc2a4\ud2b8 \uc900\ube44\uc5d0 \ub9e4\uc6b0 \uc720\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"