표시된 조상
면접 대비시간 제한8초메모리 제한512 MB
루트가 있는 트리에서 마킹 연산과 질의 연산을 처리한다. 각 질의는 주어진 노드에서 가장 가까운 마킹된 조상을 묻고, 모든 질의 결과의 합을 출력한다.
문제
N개의 노드로 이루어진 트리 T가 주어진다. 각 노드에는 1부터 N까지 번호가 붙어 있고, 노드 1은 항상 T의 루트이다. T에서 다음 두 연산을 생각하자.
- M v: (Mark) 노드 v를 표시한다.
- Q v: (Query) 노드 v에서 가장 가까운 표시된 조상의 번호를 출력한다. 처음에는 루트만 표시되어 있다. 어떤 노드는 자기 자신의 조상이다.
주어진 트리에서 이러한 연산들을 순서대로 수행하면서 각 Q 연산이 출력할 값을 계산하는 프로그램을 작성하라. 출력 파일이 너무 커지는 것을 막기 위해, 모든 질의 연산 결과의 합을 출력해야 한다. 주어진 연산 순서에서 모든 질의 연산의 결과를 계산할 수 있음은 검증되었다.
입력
첫째 줄에는 트리 T의 노드 수와 연산의 수를 나타내는 두 정수 N과 Q가 주어진다. 이 수들은 다음 조건을 만족한다. 1 ≤ N ≤ 100000, 1 ≤ Q ≤ 100000.
다음 N - 1개의 줄은 트리 T의 구조를 나타낸다. 각 줄에는 i번 노드의 부모 번호를 나타내는 정수 pi가 하나씩 주어진다 (i = 2, ... , N).
그다음 Q개의 줄에는 연산이 순서대로 주어진다. 각 연산은 "M v" 또는 "Q v" 형식이며, v는 노드 번호이다.
출력
모든 질의 연산 결과의 합을 한 줄에 출력한다.