트리와 다항식
시간 제한2초메모리 제한512 MB
부분 트리와 경로에 깊이 다항식 값을 더하는 쿼리를 수행한 뒤 각 정점의 최종값을 구한다.
문제
Nick은 1학년이다. 알고리즘 수업에서 트리를 배우고, 대수학 수업에서 다항식을 배운다. 그리고 무언가를 만들고 조합하는 것을 좋아한다. 최근에 스스로 풀지 못하는 문제를 하나 떠올렸다. Nick을 도와주자.
정점이 n개이고 1번부터 n번까지 번호가 붙은 루트 있는 트리가 주어진다. 각 정점에는 값이 하나씩 들어 있고, 처음에는 모든 값이 0이다. 정점 v에 대해 d[v]를 정점 v의 깊이라 하자. 깊이는 트리의 루트에서 v까지의 경로에 있는 정점의 수이며, 특히 루트의 깊이는 1이다.
k도 주어진다. 두 종류의 질의를 처리해야 한다.
- 정점 v와 다항식 q(t) = q0 + q1t + q2t2 + ... + qktk가 주어진다. v의 서브트리에 있는 각 정점 u에 대해, 그 정점의 값에 q(d[u])를 더한다.
- 정점 v와 다항식 q(t) = q0 + q1t + q2t2 + ... + qktk가 주어진다. 루트에서 v까지의 경로에 있는 각 정점 u에 대해, 그 정점의 값에 q(d[u])를 더한다.
모든 산술 연산은 109 + 7로 나눈 나머지로 수행한다.
모든 연산을 마친 뒤 각 정점의 값을 구하자.
입력
입력 데이터는 여러 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 수 t가 주어진다. (1 ≤ t ≤ 105)
이어서 각 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 트리의 정점 수 n과 다항식의 최대 차수 k가 주어진다. (1 ≤ n ≤ 105, 1 ≤ k ≤ 20)
다음 n개의 정수 p1, p2, ..., pn이 트리를 나타낸다. pi는 정점 i의 부모 번호이고, i가 루트이면 0이다. pi가 올바른 루트 있는 트리를 나타냄이 보장된다.
다음에는 정수 q가 주어진다. q는 질의의 수이다. (1 ≤ q ≤ 105) 다음 q개의 줄에 질의가 주어지며, 각 질의는 질의의 종류를 나타내는 정수 t(1 또는 2), 질의에 등장하는 정점 v, 그리고 다항식의 계수 k + 1개 q0, q1, ..., qk로 이루어진다. (0 ≤ qi < 109 + 7)
한 입력 데이터의 모든 테스트 케이스에서 n의 합은 105을 넘지 않는다. 마찬가지로 모든 테스트 케이스에서 q의 합도 105을 넘지 않는다.
출력
각 테스트 케이스마다 n개의 정수를 출력한다. 각 정점에 대해 모든 질의를 처리한 뒤 그 정점의 값을 출력한다. 모든 연산은 109 + 7로 나눈 나머지로 수행해야 한다.