본문 바로가기 메뉴 바로가기

PS 이야기

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

PS 이야기

검색하기 폼
  • 분류 전체보기 (141)
    • 문제 (1)
    • 해법 (18)
    • IOI (42)
      • IOI2011 (6)
      • IOI2012 (5)
      • IOI2013 (7)
      • IOI2014 (8)
      • IOI2015 (3)
      • IOI2016 (2)
      • IOI2017 (3)
      • IOI2018 (2)
      • IOI2019 (0)
      • IOI2020 (6)
    • ICPC (52)
      • 2012 대전 (3)
      • 2013 인터넷예선 (11)
      • 2014 전대프연 (1)
      • 2014 인터넷예선 (10)
      • 2014 대전 (11)
      • 2015 이후 한국대회 (6)
      • 해외리저널 (6)
      • World Finals (4)
    • Codejam (2)
      • Korea 2012 (1)
    • 우분투&서버 (0)
    • 공부 (24)
    • 잡담 (2)
  • 방명록

Tree (1)
[IOI2013 Day1] Dreaming 해법

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day1/dreaming/Dreaming ko (KOR).pdf $N-M-1$개의 간선을 새로 추가하고 나서 답이 될 수 있는 경우는 다음과 같다. 기존의 트리에 있는 최장 경로새로운 간선이 포함되는 최장 경로1번 경우를 계산하기 위해, 우리는 트리 내의 최장 경로의 길이를 구해야한다. 트리 내에 최장 경로를 트리의 '지름'이라고 말한다. 트리의 지름 구하는 방법은 여러가지가 존재하는데, 그 중 하나는 어떤 한 정점을 잡고, 그 점과 가장 먼 점 $v$를 찾고, 다시 $v$ 에서 제일 먼 경로를 찾으면 그 경로가 트리의 지름이 된다. 처음에 기존에 있는 트리들의 지름을 구하고 답으로 갱신한다. 2번 경우 해결을 ..

IOI/IOI2013 2013. 7. 22. 00:52
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
  • z-trening
  • BOI 2009
  • Dijkstra
  • BOI 2001
  • Boyer
  • ioi
  • vote
  • Boyer-Moore Majority Vote Algorithm
  • Divide & Conquer
  • IOI2013
  • Tree
  • USACO
  • Knuth Optimization
  • idea
  • Splay Tree
  • Algorithm
  • majority
  • optimization
  • dynamic programming
  • IOI2012
  • BOI
  • Greedy Method
  • Segment tree
  • TRIE
  • IOI2014
  • IOI2011
  • moore
  • HackerRank
  • Dynamic Pramming
  • Parametric Search
more
«   2025/05   »
일 월 화 수 목 금 토
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
글 보관함

Blog is powered by Tistory / Designed by Tistory

티스토리툴바