题目描述

A 国风景秀丽，由 $n$ 个城市组成，每个城市都别具一格，形成了丰富多彩的大国江山。不过遗憾的是，受金融危机的影响，A 国财政紧张，所以仅有 $n-1$ 条双向道路连接着这 $n$ 座城市。为了保证城市的方便快捷，这 $n-1$ 条道路能保证一定能从一座城市到达另一座城市。

A 国城市制度井然有序：其中 $1$ 号城市是 A 国的首都，其它每个城市都有其上属城市。具体而已对于第 $i$ 个城市到其上属城市为 $fa_i$（$1\le fa_i<i$）有一条道路，这条道路的长度为 $w_i$。我们称一个城市 $y$ 是城市 $x$ 的间接附属，当且仅当城市 $y$ 的上属城市 $fa_y$ 是城市 $x$，或者城市 $fa_y$ 是城市 $x$ 的间接附属。定义 $\mathrm{dist}(x,y)$ 表示从城市 $x$ 到城市 $y$ 的最短路径长度。

由于 A 国地势险峻、天灾频发，中央指挥部需要精确指挥调度，并平衡各城市消防安全部队的总工作量，定义城市 $i$ 消防安全部队的工作量为 $a_i$，当城市 $i$ 消防安全部队前往城市 $x$ 执行一次任务时，由于道阻且跻，所以工作量会增加 $\mathrm{dist}(i,x)$，即 $a_i\leftarrow a_i+\mathrm{dist}(i,x)$。每个城市的初始工作量是 $0$。

中央指挥部总共发出了 $q$ 条指令：

• $1\ x\ y$：执行任务：城市 $y$ 发生了一场灾难，命令城市 $x$ 及其所有间接附属的城市的消防安全部队前往城市 $y$ 前线支援，执行一次到城市 $y$ 的任务；
• $2\ x$：查询工作量：查询城市 $x$ 及其所有间接附属的城市的消防安全部队工作量的总和。

输入格式

第一行给定两个整数 $n,q(1\le n,q\le 5\times 10^5)$，分别表示城市数量和指令数量。

接下来 $n-1$ 行，每行给定两个整数 $fa_{i+1},w_{i+1}(1\le fa_{i+1}<i+1,1\le w_{i+1}\le 100)$，其中第 $i$ 行的两个整数 $fa_{i+1},w_{i+1}$ 分别表示城市 $i+1$ 的上属城市以及路径长度。

接下来 $q$ 行，每行形如：

• $1\ x\ y(1\le x,y\le n)$：表示第一类指令：执行任务；
• $2\ x(1\le x\le n)$：表示第二类指令：查询工作量。

输出格式

对于每条第二类指令，输出一行一个整数，表示总工作量。

5 4
1 3
1 2
2 1
2 2
1 5 1
2 1
1 2 3
2 2

5
23