채널 접근 권한 판정

문제

사내 메신저의 보안 담당자가 채널 접근 권한 로그를 점검한다. 채널은 1번부터 N번까지 있고, 1번 채널이 최상위이며 나머지 채널 i는 부모 채널 p_i를 가진다. (p_i < i) 규칙은 시간순으로 적용되며 다음 세 종류의 기록이 M개 주어진다. 'G u c'는 사용자 u에게 채널 c와 그 모든 하위 채널(c의 서브트리)에 대한 접근을 허용하는 규칙이고, 'R u c'는 같은 범위에 대한 접근을 회수하는 규칙이다. 단, u가 0이면 규칙은 모든 사용자에게 적용된다. 'Q u c'는 지금 이 시점에 사용자 u가 채널 c에 접근할 수 있는지 묻는 조회이다. 조회에서 u는 1 이상이다. 판정 방법은 다음과 같다. 조회 시점 이전에 기록된 규칙 중에서, 사용자 u 본인에게 적용된 규칙이거나 모든 사용자에게 적용된 규칙이고, 규칙의 채널이 c 자신이거나 c의 조상인 것만 후보로 삼는다. 후보 중 가장 늦게 기록된 규칙이 허용(G)이면 ALLOW, 회수(R)이면 DENY이다. 후보가 하나도 없으면 DENY이다. 모든 조회에 대해 판정 결과를 순서대로 출력하시오.

입력

첫 줄에 N과 M이 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ M ≤ 200,000) 둘째 줄에 p_2, p_3, ..., p_N이 공백으로 구분되어 주어진다. (1 ≤ p_i < i, N = 1이면 빈 줄이다) 이어서 M개의 줄에 시간순으로 기록이 'G u c', 'R u c', 'Q u c' 형태로 주어진다. (1 ≤ c ≤ N, G와 R의 u는 0 ≤ u ≤ 200,000, Q의 u는 1 ≤ u ≤ 200,000) 조회가 최소 하나는 존재한다.

출력

조회마다 한 줄에 ALLOW 또는 DENY를 기록 순서대로 출력한다.

5 11
1 1 2 2
G 0 1
R 3 2
Q 3 4
Q 3 3
G 3 4
Q 3 4
Q 2 5
R 0 2
Q 2 5
Q 3 5
Q 3 4

DENY
ALLOW
ALLOW
ALLOW
DENY
DENY
DENY

1 3

Q 1 1
G 1 1
Q 1 1

DENY
ALLOW

출처: Devin.KR 자체 제작