P15600 [ICPC 2020 Jakarta R] Tree Beauty

有一棵有根树，包含 $N$ 个顶点，编号从 $1$ 到 $N$。顶点 $1$ 是树的根，对于所有 $2 \leq i \leq N$，$P_i$ 是顶点 $i$ 的父节点。每个顶点都有一个美丽值，初始为 $0$。 你可以使用一台特殊机器来增加顶点的美丽值。向机器提供三个参数 $X$、$Y$ 和 $K$，机器将增加顶点 $X$ 的子树中所有顶点的美丽值。如果顶点 $X'$ 位于顶点 $X$ 的子树中，则其美丽值将增加 $\left\lfloor \frac{Y}{K^d} \right\rfloor$，其中 $d$ 是连接顶点 $X$ 到 $X'$ 的路径上的边数。例如，顶点 $X$ 的美丽值增加 $Y$，顶点 $X$ 的所有子节点的美丽值增加 $\left\lfloor \frac{Y}{K} \right\rfloor$，顶点 $X$ 的子节点的所有子节点的美丽值增加 $\left\lfloor \frac{Y}{K^2} \right\rfloor$，以此类推。 你将依次执行 $Q$ 次操作。每次操作是以下类型之一： 1. 使用特殊机器，向机器提供三个参数 $X$、$Y$ 和 $K$。 2. 报告顶点 $X$ 的子树中所有顶点的美丽值总和。 对于每个第二类操作，输出顶点 $X$ 的子树中所有顶点的美丽值总和。

输入第一行包含两个整数 $N$ 和 $Q$（$1 \leq N, Q \leq 100\,000$），分别表示顶点数量和操作数量。下一行包含 $N-1$ 个整数 $P_i$（$1 \leq P_i < i$），表示顶点 $i \in [2, N]$ 的父节点；注意 $i$ 从 $2$ 开始。接下来 $Q$ 行，每行包含以下格式之一，表示你要执行的操作： - $1\ X\ Y\ K$（$1 \leq X \leq N$；$1 \leq Y, K \leq 100\,000$） 使用特殊机器，向机器提供三个参数 $X$、$Y$ 和 $K$。 - $2\ X$（$1 \leq X \leq N$） 输出顶点 $X$ 的子树中所有顶点的美丽值总和。 保证至少有一个第二类操作。

对于每个第二类操作，按输入顺序输出一行一个整数，表示顶点 $X$ 的子树中所有顶点的美丽值总和。

#### 样例 #1 解释 树的结构如下图所示： :::align{center}  ::: - 第一次操作使顶点 $1$ 的美丽值增加 $99$，顶点 $2$ 和 $3$ 增加 $49$，顶点 $4$ 和 $5$ 增加 $24$。 - 顶点 $1$ 的子树中所有顶点的美丽值总和为 $99 + 49 + 49 + 24 + 24 = 245$。 - 顶点 $3$ 的子树中所有顶点的美丽值总和为 $49 + 24 + 24 = 97$。 - 第四次操作使顶点 $3$ 的美丽值增加 $2$，顶点 $4$ 和 $5$ 增加 $0$。 - 顶点 $3$ 的子树中所有顶点的美丽值总和为 $51 + 24 + 24 = 99$。 翻译由 DeepSeek 完成