P15600 [ICPC 2020 Jakarta R] Tree Beauty

There is a rooted tree of $N$ vertices, numbered from $1$ to $N$. Vertex $1$ is the root of the tree, while $P_i$ is the parent of vertex $i$, for all $2 \leq i \leq N$. Each vertex has a beautiness value, which is initially $0$. You can use a special machine that can increase the beautiness value of the vertices. By giving three parameters $X$, $Y$, and $K$ to the machine, the machine will increase the beautiness value of all vertices in the subtree of vertex $X$. If vertex $X'$ is in the subtree of vertex $X$, then its beautiness value will increase by $\left\lfloor \frac{Y}{K^d} \right\rfloor$, where $d$ is the number of edges in the path connecting vertex $X$ to vertex $X'$. For example, the beautiness value of vertex $X$ will increase by $Y$, the beautiness value of all children of vertex $X$ will increase by $\left\lfloor \frac{Y}{K} \right\rfloor$, the beautiness value of all children of vertex $X$'s children will increase by $\left\lfloor \frac{Y}{K^2} \right\rfloor$, and so on. You are going to perform $Q$ operations one by one. Each operation is one of the following types: 1. Use the special machine by giving three parameters $X$, $Y$, and $K$ to the machine. 2. Report the total beautiness value of all vertices in the subtree of vertex $X$. For each operation of the second type, output the total beautiness value of all vertices in the subtree of vertex $X$.

Input begins with a line containing two integers: $N\ Q$ ($1 \leq N, Q \leq 100\,000$) representing the number of vertices and the number of operations, respectively. The next line contains $N-1$ integers: $P_i$ ($1 \leq P_i < i$) representing the parent of vertices $i \in [2, N]$; note that $i$ starts from $2$. The next $Q$ lines each contains one of the following input format representing the operation you should perform. - $1\ X\ Y\ K$ ($1 \leq X \leq N$; $1 \leq Y, K \leq 100\,000$) Use the special machine by giving three parameters $X$, $Y$, and $K$ to the machine. - $2\ X$ ($1 \leq X \leq N$) Output the total beautiness value of all vertices in the subtree of vertex $X$. There will be at least one operation of the second type.

For each operation of the second type in the same order as input, output in a line an integer representing the total beautiness value of all vertices in the subtree of vertex $X$.

#### Explanation for the sample input/output #1 The tree is illustrated by the following image. :::align{center}  ::: - The first operation increases the beautiness values of vertex $1$ by $99$, vertex $2$ and $3$ by $49$, and vertex $4$ and $5$ by $24$. - The total beautiness value of all vertices in the subtree of vertex $1$ is $99 + 49 + 49 + 24 + 24 = 245$. - The total beautiness value of all vertices in the subtree of vertex $3$ is $49 + 24 + 24 = 97$. - The fourth operation increases the beautiness values of vertex $3$ by $2$ and vertex $4$ and $5$ by $0$. - The total beautiness value of all vertices in the subtree of vertex $3$ is $51 + 24 + 24 = 99$.