C-树上行走_牛客挑战赛57

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一棵 $n$ 个点的树，每个点初始有一个点权 $a_i$ ，以及一个计数器 $b_i$ ，初始 $b_i=0$ ，您需要支持：

$1.$ 给定 $x,y$ ，令 $x\rightarrow y$ 的最短路上的点构成的点序列为 $p$ ，对于所有 $i>1$ ，令 $b_{p_{i}}$ 增加 $a_{p_{i-1}}$ 。

$2.$ 给定 $x$ ，请输出 $b_x$ 的值。

输入描述:

第一行两个正整数 。

之后一行  个数，第  个数为 。

之后  行，每行两个正整数 ，表示树上存在一条  之间的边。

之后  行，每行形如  或  表示一次操作或询问。

输出描述:

对于所有询问，输出一行一个数表示答案。

示例1

输入

复制

6 8
1 10 100 1000 10000 100000
1 2
1 3
2 4
2 5
3 6
1 4 6
1 6 5
2 1
2 2
2 3
2 4
2 5
2 6

输出

复制