| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 216 | 68 | 58 | 38.667% |
레헬른의 가장 큰 볼거리는 단연 폭죽놀이다. 레헬른의 루시드는 폭죽놀이의 성공적인 마무리를 위해 고민하고 있다.
루시드는 하늘에서 폭죽이 터질 $N$개의 지점을 미리 정해 두었다. 각 지점에는 1번부터 $N$번까지 번호가 붙어 있다. 또한 각 지점을 잇는 $N-1$개의 경로가 존재하여, 임의의 두 지점을 경로만을 따라 이동할 수 있다. 즉 지점들은 1번 지점을 루트로 하는 트리 구조로 볼 수 있다.
각 폭죽은 터질 때 주위 온도에 영향을 미치며, 그 범위는 다음의 두 종류 중 하나이다.
각 폭죽에는 고유한 값 ($A,ドル $B$)가 있어 폭죽이 영향을 미치는 범위에 있는 지점의 온도가 원래 $x$였다면, 폭죽이 터진 뒤의 온도는 $Ax+B$가 된다.
루시드는 폭죽놀이가 진행될 때 원하는 지점의 온도를 실시간으로 확인할 수 있는 프로그램을 원한다. 다른 축제 준비로 너무 바쁜 루시드를 위해 프로그램을 작성해 보자. 프로그램은 다음 쿼리를 처리할 수 있어야 한다.
1 v a b: $v$번 지점에서 1번 종류의 폭죽이 터진다. 폭죽의 고유한 값은 ($a,ドル $b$)이다.2 v a b: $v$번 지점에서 2번 종류의 폭죽이 터진다. 폭죽의 고유한 값은 ($a,ドル $b$)이다.3 v: $v$번 지점의 현재 온도를 1ドル,000円,000円,007円$로 나눈 나머지를 출력한다.첫 번째 줄에 지점의 개수 $N$이 주어진다.
두 번째 줄에 각 지점의 초기 온도 $x_1, x_2, \cdots , x_N$이 공백으로 구분되어 주어진다.
세 번째 줄에 2ドル$번 지점부터 $N$번 지점까지의 부모의 번호 $p_2, p_3, \cdots , p_N$이 공백으로 구분되어 주어진다.
네 번째 줄에 쿼리의 개수 $Q$가 주어진다.
그다음 줄부터 $Q$개 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. 쿼리의 형식은 지문을 참고하여라.
주어지는 모든 입력은 정수이다.
3번 쿼리가 주어질 때마다 쿼리에서 묻는 지점의 온도를 1ドル,000円,000円,007円$로 나눈 나머지를 한 줄에 하나씩 출력하여라.
3 5 8 13 1 1 4 1 3 1 2 3 1 2 1 0 4 3 1
7 4
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 7 14 1 11 13 7 1 1 5 7 1 5 6 1 1 3 4 3 5 2 5 1 7 3 5 1 7 0 9 3 3
19 26 9
그림으로 나타내면 다음과 같다. 첫 번째 폭죽이 영향을 미치는 지점은 빨간색, 두 번째 폭죽이 영향을 미치는 지점은 파란색, 세 번째 폭죽이 영향을 미치는 지점이 노란색으로 표현되었다.