题目背景

本题时限2s，内存限制256M

题目描述

在很久很久以前，有一棵n个点的树，每个点有一个点权。

现在有q次操作，每次操作是修改一个点的点权或指定一个点，询问以这个点为根时每棵子树点权和的平方和。

（题目不是很好懂，没看太懂的可以看看样例解释）

输入格式

第一行两个整数n、q。

接下来n-1行每行两个整数a和b，表示树中a与b之间有一条边，保证给出的边不会重复。

接下来一行n个整数，第i个整数表示第i个点的点权。

接下来q行每行两或三个数，如果第一个数为1，那么接下来有两个数x和y，表示将第x个点的点权修改为y，如果第一个数为2，那么接下来有一个数x，表示询问以x为根时每棵子树点权和的平方和。

输出格式

对于每个询问输出答案。

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

121
140
194

提示

样例解释

这是一个菊花图，2与1、3、4间有边。

一开始每个点点权分别为4、3、2、1。

第一个询问以2为根，1、3、4子树中都只有本身一个点，2子树中有所有点，那么1、3、4子树中的点权和就分别是自己的点权4、2、1，2子树中的点权和就是4+3+2+1=10，$4^2+2^2+1^1+10^2=121$。

接下来将第一个点点权修改为3，每个点点权分别为3、3、2、1。

第二个询问以3为根，1、4子树中只有自己，2子树中有1、2、4，3子树中有所有点，1、4子树点权和就是自己的点权3、1，2子树点权和就是3+3+1=7，3子树点权和为3+3+2+1=9，$3^2+1^2+7^2+9^2=140$。

接下来把第二个点点权修改为4，每个点点权分别为3、4、2、1。

第三个询问以4为根，1、3子树点权和就是3和2，2子树点权和就是3+4+2=9，4子树点权和为3+4+2+1=10，$3^2+2^2+9^2+10^2=194$。

数据范围

对于10%的数据，$n,q \leq 2000$。

对于40%的数据，$n,q \leq 60000$。

对于另外30%的数据，保证每次询问的根都为1。

对于100%的数据，$1 \leq n,q \leq 200000$，$-10 \leq$输入的每个点权$\leq 10$。

建议使用输入优化~~，虽然标程没加读入优化也能过~~