네트워크 연결
시간 제한1초메모리 제한128 MB
두 클러스터를 합칠 때 항상 두 번째 클러스터의 중심을 새 중심으로 삼는 가중 합집합 연산을 수행하고, 각 회사에서 현재 클러스터 중심까지의 거리를 질의에 답하는 문제입니다.
문제
종빈이는 번부터 번까지 번호가 매겨진 개의 기업을 운영하는 아주 큰 그룹의 총수다. 처음에 각 기업은 서로 독립적인 자체 컴퓨팅·통신 센터를 가지고 있어, 각자 하나의 클러스터를 이루며 그 기업 자신이 자기 클러스터의 센터가 된다.
서비스 개선을 위해, 그룹의 CTO인 서현이는 여러 클러스터를 하나의 센터에서 관리할 수 있는 더 큰 클러스터로 합치는 다음과 같은 과정을 고안했다.
- 현재 어떤 클러스터 의 센터인 기업 를 고른다.
- 와 다른 클러스터 에 속한 기업 를 고른다(이며, 는 센터가 아니어도 된다).
- 와 를 통신 라인으로 연결한다. 이 라인의 길이는 이다.
- 클러스터 와 는 하나의 새로운 클러스터로 합쳐지며, 새 클러스터의 센터는 의 센터가 된다.
이러한 병합이 진행되는 동안, 어떤 기업이 현재 자기 클러스터의 센터까지 라인을 따라 이동하는 거리(그 경로에 놓인 라인 길이의 총합)가 얼마인지에 대한 문의가 계속 들어온다. 병합 과정을 수행하면서 이러한 거리 질의에 답하는 프로그램을 작성하여라.
입력
입력은 여러 개의 테스트 케이스로 주어진다. 첫째 줄에는 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스는 기업의 수 ()으로 시작한다. 그다음 여러 줄에 걸쳐 아래 두 가지 명령어 중 하나가 주어진다.
E I— 기업 에서 현재 클러스터의 센터까지의 거리를 출력한다.I I J— 센터 를 기업 에 연결한다(위에서 설명한 병합을 한 번 수행한다).
각 테스트 케이스는 한 글자 O로 끝난다. 각 테스트 케이스에서 명령어의 총 개수는 개를 넘지 않으며, 그중 I 명령어의 개수는 개보다 작다.
출력
각 E 명령어에 대해, 요청된 거리를 한 줄에 하나씩 출력한다.