H さんのキャンディー配り - المسألة

H さんの住む国は木を形成しています。木は $n$ 個の頂点と $n-1$ 本の辺からなる連結グラフであり、各頂点は都市です。番号 $i$ の都市には一人の子供が住んでおり、この子供はハロウィンに $a_i$ 個のキャンディをもらうことを期待しています。

H さんはハロウィンの旅程を計画します。考えられる旅程は、$m$ 個のキャンディを持って番号 $u$ の都市を出発し、唯一の最短経路を通って番号 $v$ の都市に向かい、その経路上（$u, v$ を含む）に住む子供たちにキャンディを配る（キャンディをもらえない子供がいてもよい），という形です。

H さんがキャンディを配った後、すべての子供たち（経路外の子供も含む）は、もらったキャンディの数 $a'_i$ と自分が期待していたキャンディの数 $a_i$ を比較します。ある子供の悲哀度を次のように定義します。

$$ \max\{0, a_i - a'_i\}^2 $$

H さんは、すべての子供たちの悲哀度の合計を最小化したいと考えています。

今、時間の経過順に $q$ 個のイベントが順次発生します。各イベントは以下の $2$ つのいずれかです。

1 u b：頂点 $u$ に住む子供が考えを変え、期待するキャンディの数を $b$ に変更します。つまり、$a_u$ に $b$ を代入します。この過程は以降のイベントに影響を与えることに注意してください。
2 u v m：H さんがハロウィンの旅程計画をシミュレートします。考えられる悲哀度の合計の最小値を求めてください。この過程は以降のイベントに影響を与えないことに注意してください。

$1$ 行目に、都市の数とイベントの数を表す $2$ つの正整数 $n, q$ が与えられます。

続く $n-1$ 行には、それぞれ $2$ つの正整数 $u, v$ が与えられ、木の辺を表します。同じ辺が重複して与えられないことが保証されます。

続く $1$ 行には、$n$ 個の非負整数 $a_1, a_2, \ldots, a_n$ が与えられ、各子供が期待するキャンディの数を表します。

続く $q$ 行には、それぞれ 1 u b または 2 u v m のいずれかの形式でイベントが与えられます。意味は前述の通りです。

第 $2$ 種類のイベントごとに、悲哀度の合計の最小値を表す非負整数を $1$ 行に出力してください。

3
6

すべてのデータについて、$1 \le n,q \le 10^5$、$0 \le a_i, b \le 10^9$、$0\le m \le 10^{14}$、$1 \le u, v \le n$。

小課題 1 ($10\%$)：$n,q\le 1000, m\le 1000$。

小課題 2 ($15\%$)：$n,q \le 1000$。

小課題 3 ($15\%$)：木の形状はパス（鎖）である。すなわち、木の各頂点の次数は $\le 2$。

小課題 4 ($60\%$)：追加の制約はない。

QOJ.ac