[트리] LCA, 오일러 투어, 단절점 찾기,

LCA (Lowest Common Ancestor)

• 노드 A, B의 최소 공통 조상을 찾는 것.

1. DFS/BFS를 수행해 트리의 각 노드 깊이와 부모 노드에 대해 저장한다.
2. 노드 A, B의 부모를 따라 하나씩 올라가 (depth를 맞춘 상태로 시작) 최소 공통 조상을 찾는다.
   ===> 이는 $O(N)$만큼 걸림.

• 보다 빠르게 LCA를 수행하는 방법.
  parent[K][V]=parent[k-1][parent[k-1][V]]
  : V 노드의 $2^K$번째 조상 노드
• (K, V의 순서에 따라 속도가 매우 달라짐. (2차원 배열의 구현특성 때문에))
  • 가로로 -> 이 방향으로 순회하는 것이 더 빠름.
• 우리가 갖고있는 정보. 한 노드의 바로 위의 부모 노드는 무엇인지 알고 있음. (parent[0][x])
  • 이때 parent[1][x]를 구하는 방법 : 내 부모 노드에게 물어봐야함. '너의 부모노드, 즉 1($=2^0$)칸 위의 있는 노드는 누구냐'
  • 그래서 식은 왜 k-1? : 위로 올라가는건 $2^k/2=2^{k-1}$임.
• 이때 LCA의 아래쪽 노드들은 모두 다르고, LCA의 위쪽 노드들은 모두 공통 조상이 됨.
  • 올라가서 조상이 같으면 포인터 유지 / 다르면 포인터 해당 노드로 포인터 이동
    ====> $O(\log{N})$

오일러 투어 euler tour

• dfs로 노드를 순회하여 노드에 인덱스를 붙였을 때, 이를 이용해 내 자식 노드가 어디부터 어디인지 알 수 있다.
  • 이와 누적합 개념을 이용한 문제 백준 18227

단절점 찾기

• 무향 연결 그래프에서, 어떤 노드와 그 주위 간선들을 제거했을 때 그래프가 분리된다면 그 노드는 단절점이다.
• $order_V$ : 노드 V의 방문순서 (DFS)
• $low_V$ : 노드 V 이후에 방문한 노드들 중에 이 V를 거치지 않고 방문 가능한 노드들 중 order 중 제일 작은 값이다. 초기에는 자기자신 order로 초기화되어 있다.
• $chile_V$ : 노드 V의 자식 수
• 만약 확인하고자 하는 노드 A와 이와 연결된 B에 대해서
  • A가 시작노드가 아닐 떄 : $order_A \gt low_B$ 이면 A는 단절점이다.
  • A가 시작노드일 때 : $2 \gt chile_A$ 이면 A는 단절점이다.