문제
트리 관련된 명령들이 있다.
- 노드를 추가,삭제,이동 한다.
- 노드를 특정 시점으로 되돌린다.
- 특정 노드의 하위노드 수를 구한다.
모든 명령에는 수행하는 시각 tick이 주어진다.
tick은 명령 호출 시마다 증가하는데, 반드시 1씩 증가 하는건 아니다.
명령 형식은 아래와 같다.
1. add tick uid pid
tick시각에 uid를 pid의 하위노드로 추가한다.
uid는 항상 존재하지 않으며, pid는 항상 존재한다.
2. remove tick uid
tick시각에 uid를 지운다. uid의 하위노드도 함께 지운다.
uid는 항상 존재하며 루트 노드가 아니다.
3. move tick uid pid
tick시각에 uid를 pid의 하위노드로 이동한다.
uid와 pid 모두 존재하며 다르다.
pid가 uid의 자손노드인 경우는 주어지지 않는다.
4. return tick prevTick
tick시각에 트리 상태를 prevTick 시점으로 되돌린다.
prevTick은 tick보다 항상 작다.
5. count tick uid
tick시각에 uid의 하위노드 개수를 출력한다.
uid는 항상 존재한다.
초기 트리는 1번 노드만 존재하며, 명령이 진행되는 과정에서도 항상 1번 노드가 루트 노드이다.
명령에 따라 트리를 구성하고 필요한 결과를 출력하는 프로그램을 작성하자.
입력
첫째 줄에 명령 수 Q가 주어진다.
둘째 줄부터 Q개의 줄에 걸쳐 명령이 주어진다.
Q <= 50,000
1 <= count 명령 수 <= 100
1 <= tick <= 10,000,000
1 <= uid, pid <= 50,000
출력
count 명령에 대한 결과를 한 줄에 한 개씩 출력한다.
예제 #1
13
add 1 2 1
add 2 3 1
add 3 4 2
add 4 5 2
count 5 1
add 6 6 3
add 7 7 5
add 9 8 7
count 10 3
move 11 7 3
count 12 3
return 13 4
count 14 1
4
1
3
4
예제 #2
7
add 1 2 1
add 5 4 2
add 10 5 2
add 15 7 5
remove 20 2
return 25 11
count 30 1
3
로그인해야 코드를 작성할 수 있어요.