[백준] 2927. 남극 탐험

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

문제요약

• 주어진 내용의 쿼리를 수행
• 트리에서 u부터 v까지의 합
• u의 값이 변함

접근법

• 트리는 나중에 구성한다
  • bridge가 될 수 있는 경우에만 간선을 사용함
  • bridge만 가지고서는 트리가 될 수 없기때문에 추가로 임의로 간선 구성을 해줘야함
  • 간선이 되는 것들로만 트리를 구성해나가기때문에 최종으로 봤을때 모든 노드가 이어진 트리형태가 되어도 쿼리를 처리하는데 무리가 없다
    • 어짜피 될것들은 되고, 안될것들은 안되는것을 사전에 판단해놓기 때문에
• HLD
  • 트리에서 u부터 v까지 합 처리
  • u의 값 업데이트 처리
• 오프라인 쿼리
  • 1차 쿼리 : unionfind
    • 간선이 이어질 수 있는지를 처리
      • 이어질 수 있으면 인접리스트에 추가
    • 여행경로를 수행할 수 있는지를 처리
      • 수행할 수 있으면 나중에 쿼리로 처리
  • 2차 쿼리
    • bridge 처리는 따로 하지 않음
    • 1차 쿼리에서 판단이 된것들은 바로 출력
    • 여행경로 합을 구하는 쿼리 수행후 출력