문제
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가지이기 때문이다.
트리에 대한 정보와 일련의 연산이 주어질 때, 각 연산을 효과적으로 실행하는 프로그램을 작성하시오.
입력
다음 정보가 표준 입력으로 주어진다.
첫째 줄에는 앞에서 설명한 트리의 노드 개수를 나타내는 정수
이어서 K줄에 걸쳐 각 연산에 관한 정보가 한 줄에 하나씩 주어지는데, 각 줄에는 연산의 종류를 나타내는 정수
r=1일 경우엔 연산이 paint임을 의미하며, 세 정수
r=2일 경우엔 연산이 move임을 의미하며, 두 정수
r=3일 경우엔 연산이 count임을 의미하며, 두 정수
노드의 개수가 N인 트리의 초기 모양은 그림 1에서 보인 것처럼 0번 노드가 루트이고, 나머지 노드들의 부모 노드는 0번 노드이며,
초기 트리의 모든 에지 색깔은 0이라고 가정한 사실을 기억하기 바란다.
또한, paint와 count 연산 시 a번 노드와 b번 노드사이의 최단경로의 길이는 항상 1,000 이하이다.
출력
다음 정보를 표준 출력으로 출력한다.
입력에서 주어진 count 연산 각각에 대해, 그 순서대로 그 때의 결과 값을 한 줄에 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 8점 | move 연산(즉, |
| #2 | 18점 | 5 |
| #3 | 28점 | 5 |
| #4 | 46점 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
예제1
68
213
253
1548
345
234
1037
325
342
1
3
2
예제2
715
232
243
253
262
316
1332
1165
1423
1254
1207
346
341
232
322
356
1
3
4
0
2