题目描述
从前有一棵以$1$为根的有根树，树的每个节点有一个权值。
现在请你维护如下操作：
- 1、令以节点$x$为根的子树每个节点权值增加$y$
- 2、询问节点$x$到节点$y$的路径上所有节点的权值和。
输入格式
第一行两个整数$n$，$m$，分别表示树的节点数及操作数。
接下来$n-1$行每行两个整数$x$、$y$，表示树中的一条边。
接下来$m$行每行一个操作
其中
“1 x y”表示令以节点$x$为根的子树每个节点权值增加$y$
“2 x y”表示询问节点$x$到节点$y$的路径上所有节点的权值和
输出格式
对于每个“2 x”的询问，输出其结果。
样例数据
输入1
9 2
1 2
2 3
2 4
4 5
1 6
6 7
6 8
6 9
1 2 10
2 3 6输出1
20数据规模与约定
对于$50\%$的数据，$m≤200000$
对于$80\%$的数据，$m≤500000$
对于$100\%$的数据，$n≤100000,m≤650000,x≤n,|y|≤3141592$。