데옴's 기록장

  • 홈
  • 태그
  • 방명록

offline queries 1

BOJ 13306 - 트리

그냥 문제가 너무 길다. 문제를 요약하자면 모든 정점들이 어느 한 정점으로 연결되어 있는 트리가 있고 두가지 쿼리가 주어진다. 1. 두 정점의 간선을 끊는다 2. 선택한 정점과 연결된 정점들의 개수를 센다. 일반적인 방법으로는 문제를 해결하기에는 어려워보인다. 1번 쿼리는 n-1개 들어오기 때문에 최종 상태에서는 모든 정점들이 서로 연결되어 있지 않음을 알 수 있다. 그러면 여기서 쿼리를 거꾸로 수행해보고 싶은 생각이 들 수 있다. 간선을 끊는 쿼리를 구현하는 것은 어려우므로 쿼리를 거꾸로 실행하게 되면 간선을 추가하는 쿼리로 바뀌게 된다! 여기서 바로 유니온 파인드를 사용할 수 있다. 1번 쿼리가 들어오면 두 정점을 유니온 하고 2번 쿼리가 들어오면 연결된 정점들의 개수를 세어주기만 하면 된다. 정점들..

PS & BOJ 2024.04.18
이전
1
다음
더보기
프로필사진

디미고 재학중인 고등학생입니다. 백준 문제풀이, 드림핵 문제풀이, 디미고일상을 올립니다. 알고리즘에 관한 내용은 https://blog.naver.com/playdeom에 올립니다.

  • 분류 전체보기 (37)
    • 게시판 (0)
    • 일기 (6)
      • 디미고 (3)
      • 일상 (3)
    • Hacking (3)
    • PS & BOJ (28)
    • Coding Note (0)

Tag

문법, Dynamic Programming, offline queries, rev, sorting, 적응기, segment tree, 파이썬, mathematics, Greedy, number theory, data_structure, 디미고, Dreamhack, union_find, 후기, priority_queue, 기초, Segment Tree With Lazy Propagation, Recursion,

최근글과 인기글

  • 최근글
  • 인기글

최근댓글

공지사항

페이스북 트위터 플러그인

  • Facebook
  • Twitter

Archives

Calendar

«   2025/08   »
일 월 화 수 목 금 토
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

방문자수Total

  • Today :
  • Yesterday :

Copyright © Kakao Corp. All rights reserved.

티스토리툴바