시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 15 6 5 35.714%

문제

1번 정점이 루트인 N개의 정점으로 구성된 트리가 주어진다.

처음에 모든 정점들은 0의 가중치를 가지고 있다. Q의 쿼리가 주어진다. 쿼리는 다음 2가지 중 하나이다.

  • 유형 1: 입력으로 “1 v x k”가 주어진다. 정점 v의 가중치에 x를 더한다. 정점 v와 거리가 1인 모든 자식 노드들의 가중치에는 x-k를 더한다. 정점 v와 거리가 i(i>1)인 모든 자식 노드들의 가중치에는 x-(i × k)만큼을 더한다. (1 ≤ v ≤ n, 0 ≤ x, k < 109+7)
  • 유형 2: 입력으로 “2 v”가 주어진다. 정점 v의 가중치를 109+7로 나눈 나머지를 출력한다. (1 ≤ v ≤ n)

입력

첫 번째 줄에 정점의 개수 N(1≤N≤300000)과 쿼리의 개수 Q(1≤Q≤300000)가 주어진다.

둘째 줄에 N-1개의 정수 p2, p3, ... , pn이 주어진다. pk(1 ≤ pk  < k)는 정점 k의 부모를 나타낸다.

셋째 줄부터 Q개의 줄에 걸쳐 쿼리가 주어진다. 각 쿼리의 첫 번째 정수 q는 1 또는 2의 값을 가지는 정수인데, 해당 쿼리가 어느 유형에 속하는지를 알려주는 값이다. 이후 해당 유형에 따른 정보가 주어진다.

출력

유형 2가 입력으로 주어질 때마다 유형 2의 결과를 출력한다.

예제 입력 1

3 3
1 1
1 1 2 1
2 1
2 2

예제 출력 1

2
1

출처