AT_s8pc_4_g.Get the Salary of Atcoder

问题描述

Atcoder公司有 $N$ 名员工，编号为 $0$ 至 $N−1$ ，工人 $i$ 的直接上司是 $p_i$ ，工资目前是 $a_i$ ，上下级形成了树形结构。( $p_i<i$ ，特别地， $p_0=−1$ ，因为员工 $0$ 代表老板。)

在Atcoder中，某个员工的上司的上司的上司...（重复 $k$ 次）称之为他的“第 $k$ 级上司”，而“第 $k$ 级下属”则反之亦然。

处理 $Q$ 个操作：

第一类操作: 给你 $v_i,d_i,x_i$ 。将 $v_i$ 号员工，以及他的所有 $j(1\leq j\leq d_i)$ 级下属的工资提高 $x_i$ 。

第二类操作: 给你 $v_i,d_i$ 。查询 $v_i$ 号员工以及他的所有 $j(1\leq j\leq d_i)$ 级下属的工资总和。、

第三类操作: 给你 $pr_i,ar_i$ ，表示一名新员工 $c$ 要加入Atcoder！（当然， $c$ 等于当前的员工总数。）他的直接上司是 $pr_i$ ，初始工资是 $ar_i$ 。

$N\ \ \ \ Q$

$p_0\ \ \ \ \ a_0$

$p_1\ \ \ \ \ a_1$

$\ :$ $\ \ \ \ \ \ \ :$

$p_{N-1}\ a_{N-1}$

$query_0$

$query_1$

$\ :$

$query_{Q−1}$

​$query_i$ 的格式为以下三种之一：​

$1\ v_i\ d_i\ x_i$

$2\ v_i\ d_i$

$3\ pr_i\ ar_i$

对于每个第二种询问，输出一行一个整数，表示结果。

$N≤400000$ , $Q≤50000$ , $p_i<i$​

$d_i ≤ 400000$ , $0≤a_i,x_i≤1000$

在所有询问 $1$ 和 $2$ 中，员工 $v_i$ 存在。