아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

홍준이와 트리

시간 제한2초메모리 제한512 MB

요약
부분 트리에 거리에 따라 달라지는 값을 더하는 갱신을 처리하며, 정점 하나의 가중치를 1e9+7로 나눈 나머지를 답한다.
난이도

어려움10점 중 8점

유형
트리, DFS, 누적 합, 동적 계획법
정답자
아직 제출이 없습니다

문제

1번 정점이 루트인 정점 NN개짜리 트리가 주어진다. 처음에 모든 정점의 가중치는 0이다.

쿼리 QQ개를 주어진 순서대로 처리한다. 쿼리는 두 종류다.

  • 유형 1: 1 v x k 형태로 주어진다. 정점 vv의 가중치에 xx를 더하고, vv의 서브트리에 속하면서 vv와 거리가 ii인 모든 정점의 가중치에 x−i×kx - i \times k를 더한다. (1≤v≤N1 \le v \le N, 0≤x,k<109+70 \le x, k < 10^9+7)
  • 유형 2: 2 v 형태로 주어진다. 정점 vv의 현재 가중치를 109+710^9+7로 나눈 나머지를 출력한다. (1≤v≤N1 \le v \le N)

가중치는 음수가 되기도 한다. 유형 2의 답은 항상 0 이상 109+610^9+6 이하의 나머지다.

입력

첫째 줄에 정점의 개수 NN과 쿼리의 개수 QQ가 주어진다. (1≤N≤300 0001 \le N \le 300\,000, 1≤Q≤300 0001 \le Q \le 300\,000)

둘째 줄에 N−1N-1개의 정수 p2,p3,…,pNp_2, p_3, \dots, p_N이 주어진다. pkp_k는 정점 kk의 부모이고 1≤pk<k1 \le p_k < k를 만족한다. NN이 1이면 둘째 줄은 빈 줄이다.

셋째 줄부터 QQ개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 각 줄의 첫 정수는 쿼리의 유형을 나타내고, 그 뒤에 유형에 맞는 정수가 이어진다.

출력

유형 2 쿼리마다 답을 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.

예제4

  1. 예제 1

    입력
    3 3
1 1
1 1 2 1
2 1
2 2
    예상 출력
    2
1

  2. 예제 2

    입력
    6 7
1 2 3 4 5
1 1 5 3
2 1
2 2
2 3
2 4
2 5
2 6
    예상 출력
    5
2
1000000006
1000000003
1000000000
999999997

  3. 예제 3

    입력
    6 8
1 1 1 1 1
1 1 10 4
2 2
2 6
1 3 7 2
2 3
2 1
1 6 0 0
2 6
    예상 출력
    6
6
13
10
6

  4. 예제 4

    입력
    7 9
1 1 2 2 3 3
1 1 100 7
2 4
1 2 50 20
2 4
2 5
2 6
1 4 1 1000000000
2 4
2 1
    예상 출력
    86
116
116
86
117
100