py第五天
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def dfs(u, fa):
  # 预处理
  deep[u] = deep[fa] + 1
  p[u][0] = fa
  for i in range(1, 21):
    p[u][i] = p[p[u][i - 1]][i - 1]
  for v in G[u]:
    if v == fa: continue
    dfs(v, u)

def lca(x, y):
  if deep[x] < deep[y]:
    x, y = y, x
  for i in range(20, -1, -1):
    if deep[p[x][i]] >= deep[y]:
      x = p[x][i]

  if x == y:
    return x
  for i in range(20, -1, -1):
    if p[x][i] != p[y][i]:
      x, y = p[x][i], p[y][i]
  return p[x][0]

n = int(input())
G = [[] for i in range(n + 1)]
deep = [0] * (n + 1) # deep[u]表示节点u的深度
p = [[0] * 21 for i in range(n + 1)] # p[u][i]表示节点u往上走2^i到达的节点

for _ in range(n - 1):
  u, v = map(int, input().split())
  G[u].append(v)
  G[v].append(u)

dfs(1, 0)
Q = int(input())
for _ in range(Q):
  x, y = map(int, input().split())
  print(lca(x, y))
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇