문제
초기에 0번 노드 한개로만 구성된 트리가 존재한다.
트리에 노드를 추가, 삭제, 이동하며 트리를 새롭게 구성해나간다. (트리의 root는 항상 0임이 보장된다)
그 과정에서 노드 x에 대해 (1) root 노드와의 거리 (2)가장 멀리 있는 자손 노드와의 거리를 확인할 수 있어야 한다.
아래 주어지는 명령 형식에 맞게 프로그램을 작성하자.
(0 <= x, y <= 10,000)
1. add x y
x를 y의 자식 노드로 추가한다.
x는 1부터 1씩 증가하며 주어진다.
y가 존재하지 않는 경우는 주어지지 않는다.
2. remove x
x인 노드를 지운다.
x의 모든 자식노드는 x의 부모노드의 자식노드가 된다.
x가 root이거나 존재하지 않는다면 무시한다.
3. move x y
x를 y의 자식노드로 변경한다.
x 또는 y 노드가 존재하지 않거나 y가 x의 자손 노드이거나 혹은 x==y면 무시한다.
4. query x
x의 root와의 거리를 a
x와 가장 먼 자손 노드와의 거리를 b라 할 때,
a, b를 각각 구해서 출력한다.
x가 존재하지 않는 경우는 주어지지 않는다.
입력
첫 줄에 쿼리수 Q(<= 10,000)가 주어진다.
둘째 줄부터 Q개 줄에 걸쳐 명령이 한 줄에 한 개씩 주어진다. (0 <= x, y <= 10,000)
출력
query 명령마다 한 줄에 a, b를 한 칸 띄고 출력한다.
예제 #1
10
add 1 0
add 2 0
add 3 1
add 4 1
query 1
move 1 2
query 1
query 2
remove 1
query 2
1 1
2 1
1 2
1 1
예제 #2
18
add 1 0
add 2 0
add 3 1
add 4 3
add 5 2
add 6 5
query 2
query 4
add 7 5
remove 10
remove 1
remove 5
add 8 2
add 10 7
query 2
query 8
move 2 3
query 3
1 2
3 0
1 2
2 0
1 3
출처
teriusu
로그인해야 코드를 작성할 수 있어요.