N개의 노드로 구성된 루트가 있는 트리가 다음과 같이 주어진다.

각 노드는 0부터 N-1까지의 번호로 구별되고, 0번 노드는 루트 노드이고, 나머지 노드 각각은 0번 노드의 자식 노드이다.

트리에 적용할 수 있는 연산은 세 종류이며, 이를 통해 트리의 모양을 바꾸거나 트리 에지에 색칠을 할 수 있다.

각 연산과 그 의미는 다음과 같다.

1. paint(a, b, c): a번 노드와 b번 노드를 잇는 최단경로를 찾은 후, 경로 상에 있는 모든 에지를 색깔 c로 칠한다.

2. move(a, b): a번 노드의 부모 노드를 b번 노드로 바꾼다. 단, b번 노드는 a번 노드를 루트로 하는 부트리(subtree)에 속하지 않는다. 부모 노드를 바꾸기 전 a번 노드의 부모 노드를 p라 할 때, 새로운 에지 (a, b)는 원래의 에지 (a, p)의 색깔을 갖는다.

3. count(a, b): a번 노드와 b번 노드를 잇는 최단경로를 찾은 후, 그 경로 사이에 있는 에지에 칠해진 서로 다른 색깔의 개수를 출력한다.

에지에 칠하는 색깔 c를 정수로 표시한다. 그리고 처음에는 모든 에지의 색깔이 0이라고 가정한다.

예를 들어, 그림 1에서 보인 것처럼 6개의 노드로 구성된 초기 트리에 적용된 연산이

차례로 move(1,3); move(5,3); paint(5,4,8); move(3,4); paint(0,3,7); count(2,5); 일 때,

각 연산을 실행한 후 어떻게 트리의 모양과 에지 색깔이 바뀌는지를 아래 그림 2부터 그림 4에서 차례대로 보였다.

그리고, 마지막 연산 count(2,5)에 대한 결과로는 3을 출력하게 된다.

왜냐하면, 그림 4의 우측 그림에서 보듯이 2번 노드와 5번 노드 사이의 최단 경로 상에 있는 에지들에 칠해진 색깔이 {0, 7, 8}로 3가지이기 때문이다.

트리에 대한 정보와 일련의 연산이 주어질 때, 각 연산을 효과적으로 실행하는 프로그램을 작성하시오.

#2916 upload 3187 done 579 how_to_reg 436

트리 timer 2s memory 128MB

#2916

트리 2s 128MB