原试题 pdf 见附件。
你是能看到第一题的 friends 呢。 ——hja
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没 什么关系。
还记得我们在课上讲过这么一道题，给定一棵树，有三种不同的操作，询问子树点权和、修改子树链权值和换根操作。现在我们把这个题换一下，变成一个新的问题，你需要支持以下三种操作：
询问树上一条链的点权和。
将某个点点权 +v 。
将树的根换为点 p 。
第一行两个整数 N, M 代表树的点数和操作次数。
接下来一行 N 个数代表树上每个点的点权。
接下来 N - 1 行每行两个数代表树上一条边。
接下来 M 行，每行第一个数 opt 代表操作的种类数。如果 opt = 1 ，接下来会有两个数 p_1, p_2 代表询问的两个点；如果 opt = 2 ，接下来会有两个数 p, v ；如果 opt = 3 ，接下来会有一个数 p 。
对于每个第一种操作，输出一行一个数代表答案。
3 3 1 2 3 1 2 2 3 1 1 3 2 1 1 1 1 3
6 7
对于 40\% 的数据， N, M \leq 1000 。
对于另外 20\% 的数据，没有操作 3。
对于 90\% 的数据，没有操作 2。
对于 100\% 的数据， 1 \leq N, M \leq 10^5 ，所有点初始点权以及 v 都不超过 1000 。