Informatica Online Judge

  변형된 트리(Large) [1920 / 0780]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 1   Total Tried : 2


The Champion of this Problem (C++) : gs16024 - 19ms / 2674byte
My Best Submission (C++) : N/A

[koistudy.net (34th 김현수)]
Writer ID : [gs16024]

Background

현수는 2016 KOI 트리를 풀던 중 새로운 문제가 생각났다. 현수를 도와 문제를 해결하자



트리 T는 위 그림 1과 같은 구조를 가지고 있으며 원은 ‘정점’이라 하고, 정점과 정점을 연결하 는 선을 ‘에지’라 한다. 특히 가장 위에 위치한 정점을 ‘루트’라 하는데 오직 하나만 있다. N개의 정점들은 숫자 1부터 N으로 표현하고 루트는 항상 1이다.

위에서부터 차례대로 트리 T에 루트부터 level을 매긴다. 루트의 level은 1이고 루트의 자식의 level은 2, 루트의 자식의 자식의 level은 3, 루트 자식의 자식의......

한 정점 v의 최고 조상을 v와 같은 트리에 있는 정점 중 level이 가장 작은 정점이라 정의 하자
현수는 한 정점 v에 대하여 최고 조상의 level이 얼마인지 궁금해졌다
트리 T에서 어떤 두 정점을 연결하는 에지를 제거해도 노드의 높이는 유지된다.

하나의 트리 정보가 주어지고, 에지의 제거 정보와 질의가 임의의 순서로 주어질 때, 작업을 순서대로 수행하며 질의에 대한 답을 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄 에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (2≤N,Q≤200,000)가 주어진다.

다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 a가 주어 진다 (1≤a≤N). 루트는 항상 1이다.

다음 Q 개의 줄 각각에는 두 정수 b, c (2≤c≤N)가 주어진다.

b=0이면 c의 최고 조상의 level을 구해 출력한다.
만약 c의 최고 조상의 level이 홀수이고 c와 c의 부모간의 간선이 있으면 삭제한다.

b=1이면 c와 c의 부모간의 간선이 있으면 삭제하고, 간선이 없으면 아무런 작업도 하지 않는다.

Output

질의에 대한 답을 순서대로 출력한다.

IO Example

입력
11 7
7
4
1
9
11
1
11
1
3
7
0 8
0 8
1 3
0 2
0 10
1 11
0 8


출력
1
4
1
3
4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]