题目描述

小 R 指挥的装甲军团的海上补给线被敌军截断了，只能依靠稀少的空投补给来维持部队战斗力。

当前的战线呈一棵有 $n$ 个节点的树的形状，树上每一个节点都是重要的战略要点，第 $i$ 个节点的初始补给匮乏度为 $a_i$。若在一次空投补给后第 $i$ 个节点得到了 $b_i$ 的补给，则定义战况恶化度为 $\sum_{i=1}^n{\max(0,a_i-b_i)^2}$。

然而战局并非一成不变的，因此小 R 给你了 $q$ 次询问。

每次询问可能是以下两种类型之一：

1.战局发生了变化，点 $x$ 的补给匮乏度 $a_x$ 变为了 $v$。

2.一队补给机将携带 $m$ 的补给由 $u$ 沿树上最短路径飞到 $v$，可以向经过的节点空投总和不超过 $m$ 的补给，你需要求出这次空投后的最小战况恶化度。（注意，这和后续询问是独立的，即不会对 $a$ 数组造成修改）

输入格式

第一行两个正整数 $n,q$, 表示节点个数与询问个数。

接下来 $n−1$ 行，每行两个正整数 $u,v$ 表示树的一条边。保证不会重复给出同一条边。

接下来一行 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$​，表示每个节点的初始补给匮乏度。

接下来 $q$ 行每行可能为 1 u b 与 2 u v m 两种形式之一，含义如上所述。

输出格式

对于每一个第二类询问，输出一行一个数代表最小战况恶化度。

输入输出样例 #1

输入 #1

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

输出 #1

3
6

输入输出样例 #2

输入 #2

见下发文件

输出 #2

见下发文件

说明/提示

2500ms，512MB

对于所有数据，满足 $n,q \leq 10^5, 0 \leq a_i,v \leq 10^9, 0 \leq m \leq 10^{14}, 1 \leq u,v \leq n$。

$\text{Subtask 1(15pts)}:$ $n,q,m \leq 1000$。

$\text{Subtask 2(15pts)}:$ $n,q \leq 1000$。

$\text{Subtask 3(10pts)}:$ 保证对于任意 $1 \leq i < n$，存在边 $(i,i+1)$。

$\text{Subtask 4(15pts)}:$ $n,q \leq 20000$。

$\text{Subtask 5(15pts)}:$ $n,q \leq 50000$。

$\text{Subtask 6(30pts)}:$ 无特殊限制。

友情提示：请多看一眼数据范围。

Download

样例数据