moner_ari   1년 전

[문제]

정점이 N개인 트리 T가 주어집니다. 각 정점의 번호는 1번부터 N번까지이며, T의 루트 정점은 항상 1번 정점입니다. 이때 다음과 같이 T에 대한 2가지 연산을 정의합시다.

  • M v: (표시) 정점 v를 색칠합니다.
  • Q v: (쿼리) 정점 v에서 가장 가까운 색칠된 조상의 번호를 출력합니다. 처음에는 루트 정점에만 색이 칠해져 있습니다. 각 정점은 자기 자신의 조상임을 유의합니다.

여러분은 트리가 주어졌을 때, 위의 2가지 연산을 수행하고 'Q v' 연산이 주어질 때마다 출력할 값을 계산하는 프로그램을 만들어야 합니다. 출력 양이 너무 많아지는 것을 방지하기 위해, 여러분의 프로그램은 'Q v' 연산의 결과를 모두 합친 값을 출력해야 합니다. 참고로 위 연산들이 어떻게 주어지든, 'Q v' 연산이 주어질 때마다 결과 값을 계산하는 것이 항상 가능합니다.

--------

[입력]

입력의 첫 줄에는 트리 T의 정점의 개수 N과 연산 횟수 Q가 주어집니다. 이때 1 ≤ N ≤ 100000, 1 ≤ Q ≤ 100000입니다.

다음 N - 1개 줄에는 트리 T의 구조가 주어집니다. 각 줄에는 i번 정점의 부모 정점의 번호 pi (i = 2, 3, ..., N)가 주어집니다.

다음 Q개 줄에는 연산이 순서대로 주어집니다. 각 연산은 "M v", "Q v" 형태로 주어지며, v는 정점의 번호입니다.

--------

[출력]

쿼리 연산의 결과 값을 모두 합친 값을 출력합니다.

댓글을 작성하려면 로그인해야 합니다.