Update 5.py

ndb796 · web-flow · commit 171b28e0c258 · 2020-11-02T15:23:57.000+09:00
diff --git a/21/5.py b/21/5.py
@@ -0,0 +1,46 @@
+import sys
+sys.setrecursionlimit(int(1e5)) # &#47088;&#53440;&#51076; &#50724;&#47448;&#47484; &#54588;&#54616;&#44592; &#50948;&#54620; &#51116;&#44480; &#44618;&#51060; &#51228;&#54620; &#49444;&#51221;
+
+n = int(input())
+
+parent = [0] * (n + 1) # &#48512;&#47784; &#45432;&#46300; &#51221;&#48372;
+d = [0] * (n + 1) # &#44033; &#45432;&#46300;&#44620;&#51648;&#51032; &#44618;&#51060;
+c = [0] * (n + 1) # &#44033; &#45432;&#46300;&#51032; &#44618;&#51060;&#44032; &#44228;&#49328;&#46104;&#50632;&#45716;&#51648; &#50668;&#48512;
+graph = [[] for _ in range(n + 1)] # &#44536;&#47000;&#54532;(graph) &#51221;&#48372;
+
+for _ in range(n - 1):
+    a, b = map(int, input().split())
+    graph[a].append(b)
+    graph[b].append(a)
+
+# &#47336;&#53944; &#45432;&#46300;&#48512;&#53552; &#49884;&#51089;&#54616;&#50668; &#44618;&#51060;(depth)&#47484; &#44396;&#54616;&#45716; &#54632;&#49688;
+def dfs(x, depth):
+    c[x] = True
+    d[x] = depth
+    for y in graph[x]:
+        if c[y]: # &#51060;&#48120; &#44618;&#51060;&#47484; &#44396;&#54664;&#45796;&#47732; &#45336;&#44592;&#44592;
+            continue
+        parent[y] = x
+        dfs(y, depth + 1)
+
+# A&#50752; B&#51032; &#52572;&#49548; &#44277;&#53685; &#51312;&#49345;&#51012; &#52286;&#45716; &#54632;&#49688;
+def lca(a, b):
+    # &#47676;&#51200; &#44618;&#51060;(depth)&#44032; &#46041;&#51068;&#54616;&#46020;&#47197;
+    while d[a] != d[b]:
+        if d[a] > d[b]:
+            a = parent[a]
+        else:
+            b = parent[b]
+    # &#45432;&#46300;&#44032; &#44057;&#50500;&#51648;&#46020;&#47197;
+    while a != b:
+        a = parent[a]
+        b = parent[b]
+    return a
+
+dfs(1, 0) # &#47336;&#53944; &#45432;&#46300;&#45716; 1&#48264; &#45432;&#46300;
+
+m = int(input())
+
+for i in range(m):
+    a, b = map(int, input().split())
+    print(lca(a, b))
