레이팅 미적용농부 존은 소들이 너무 빽빽하게 모여 있으면 다투는 경향이 있다는 것을 알아차리고, 소들을 넓게 분산시키기 위해 새 헛간들을 연이어 지으려고 한다.
농부 존이 새 헛간을 지을 때마다, 그는 그 헛간을 기존의 헛간 하나와 최대 한 개의 양방향 통로로 연결한다. 소들이 충분히 멀리 떨어져 있는지 확인하기 위해, 그는 때때로 특정 헛간에서 도달 가능한 가장 먼 헛간까지의 거리를 알고 싶어 한다(두 헛간 사이의 거리는 한 헛간에서 다른 헛간으로 가기 위해 지나야 하는 통로의 개수이다).
농부 존은 총 \(Q\)개(\(1 \leq Q \leq 10^5\))의 질의를 하는데, 각 질의는 "건설" 또는 "거리" 중 하나이다. 건설 질의에서는 농부 존이 헛간을 하나 짓고 이전에 지어진 헛간 최대 한 개와 연결한다. 거리 질의에서는 농부 존이 특정 헛간에서 일련의 통로를 통해 도달 가능한 가장 먼 헛간까지의 거리를 묻는다. 질의된 헛간은 이미 지어져 있음이 보장된다. 농부 존이 이 모든 질의에 답하도록 도와주자.
출제자: Anson Hu
출제자: Anson Hu
첫째 줄에 정수 \(Q\)가 주어진다. 다음 \(Q\)개의 줄에는 각각 질의가 하나씩 주어진다. 각 질의는 "B p" 또는 "Q k"의 형태로, 각각 헛간을 짓고 헛간 \(p\)와 연결하라는 것, 또는 헛간 \(k\)에서 앞서 정의한 가장 먼 거리를 답하라는 것이다. \(p = -1\)이면 새 헛간은 어떤 헛간과도 연결되지 않는다. 그렇지 않으면 \(p\)는 이미 지어진 헛간의 번호이다. 헛간 번호는 \(1\)부터 시작하므로, 첫 번째로 지어진 헛간이 헛간 \(1\), 두 번째가 헛간 \(2\), 이하 같은 식이다.
각 거리 질의마다 한 줄씩 출력한다. 다른 어떤 헛간과도 연결되지 않은 헛간의 가장 먼 거리는 \(0\)임에 유의하라.
newbarn.in · 출력을 쓸 파일 newbarn.out7
B -1
Q 1
B 1
B 2
Q 3
B 2
Q 20
2
1The example input corresponds to this network of barns:
(1)
\
(2)---(4)
/
(3)
In query 1, we build barn number 1. In query 2, we ask for the distance of 1 to
the farthest connected barn. Since barn 1 is connected to no other barns, the
answer is 0. In query 3, we build barn number 2 and connect it to barn 1. In
query 4, we build barn number 3 and connect it to barn 2. In query 5, we ask for
the distance of 3 to the farthest connected barn. In this case, the farthest is
barn 1, which is 2 units away. In query 6, we build barn number 4 and connect it
to barn 2. In query 7, we ask for the distance of 2 to the farthest connected
barn. All three barns 1, 3, 4 are the same distance away, which is 1, so this is
our answer.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > February > Platinum