题目描述

从前有一棵以$1$为根的有根树，树的每个节点有一个权值。

现在请你维护如下操作：

• 1、令以节点$x$为根的子树中所有节点的权值增加$y$
• 2、询问以节点$x$为根的子树中所有节点的权值和。

输入格式

第一行两个整数$n$，$m$，分别表示树的节点数及操作数。

接下来$n-1$行每行两个整数$x$、$y$，表示树中的一条边。

接下来$m$行每行一个操作，其中“1 x y”表示将以节点$x$为根的子树中所有节点的权值增加$y$，“2 x”表示询问以节点 $x$ 为根的子树中所有节点的权值和。

输出格式

对于每个“2 x”的询问，输出其结果。

样例数据

输入1

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

输出1

4
7

数据规模与约定

对于$100\%$的数据，$n≤100000,m≤200000,x≤n,|y|≤1000000$。

Data:出题人——syxx_chenyuyang