U641706 世界树

题目背景

「世界树」是一颗有 $n$ 个节点，并且以 $1$为根节点的树。平日里，「智慧之神」纳西妲掌管着世界树的一切。有一天，纳西妲发现这棵树被「智障之神」纳东妲污染了。但是纳西妲觉得纳东妲实在太智障了，她只需要 $O(1)$ 就可以恢复世界树。于是她决定考验一下你，为了证明自己，你需要解决这道题。

当然，由于你不是「智慧之神」，你无法在 $O(1)$ 的时间内解决问题。（如果你 $O(1)$ 做出来了我请你抽烟）

题目描述

给定一颗 $n$ 个结点的树（根节点为 $1$），每个节点有一个权值，并给出 $q$ 个询问。

每个询问的形式如下：

1. 1 x k表示纳东妲会污染节点 $x$ 及其子树，将其中每个节点的值加上 $k$。
2. 2 x y表示如果纳西妲选择根节点分别为 $x$ 和 $y$ 的两颗子树进行恢复，其代价为分别在两颗子树中的两两节点权值之积的总和。（注：该操作并不会改变权值大小）

对于每个询问 $2$，你需要回答出其代价。（答案对1145141919取模）

输入格式

第一行输入两个正整数 $n,q$，表示节点个数和询问个数。

第二行输入 $n$ 个正整数 $a_i$，其中 $a_i$ 表示节点 $i$ 的权值。

接下来 $n - 1$ 行，每行两个正整数 $u,v$，表示和 $u$ 和 $v$ 之间有一条边。

接下来 $q$ 行，每行一个询问。

输出格式

对于每个询问 $2$，输出一行一个正整数，表示其代价。

输入输出样例 #1

输入 #1

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

输出 #1

42
90
252

说明/提示

对于 $100\%$ 的数据，$1 \le n,q \le 10^5,1\le u,v,x,y \le n,1\le a_i,k \le 10^9$。

后来，纳东妲将每个节点的值都设置为了NaN，不知不觉的睡着了，纳西妲趁着这个好机会，$O(1)$ 恢复了世界树，并使用宇宙射线远程轰击他的抽卡系统让她每次都吃满大保底，非的他不敢还手，对他的打击比号被融了还大。