标题只是为了吸引你点进来的。

题目描述

有一棵 $n$ 个点的树与 $n$ 个集合 $S_i$，初始时 $S_i = \{i\}$，树上每个节点有一个权值 $a_i$，对于一个集合 $S$ 与两个节点 $u,v$ 而言，令 $t = 0$，然后依次遍历树上 $u$ 到 $v$ 的简单路径经过的节点，假若遍历到的节点 $i$ 属于集合 $S$ 那么让 $q \gets t + a_i$ 否则让 $q \gets t - a_i$，将最后抵达节点 $v$ 后 $t$ 的值定义为 $\text{cost}(S,u,v)$（此时节点 $v$ 对 $t$ 的改变已经完成），再定义一个集合的权值 $\text{val}(S) = \sum_{u \in S} \sum_{v \in {S \setminus u}} \text{cost}(S,u,v)$。现在有 $q$ 次事件。每次事件形如 $u,v$ 表示令 $S_u \gets S_u \cup S_v$ 并删除集合 $S_v$，事件结束后你需要回答 $\text{val}(S_u)$ 对 $2^{32}$ 取模后的值，保证事件开始前集合 $S_u,S_v$ 均未被删除。

输入格式

第一行两个数 $n,q$。

接下来 $n-1$ 行每行两个数 $u,v$ 代表树上一条边。

再接下来一行 $n$ 个数表示 $a_i$。

再接下来 $q$ 行每行两个数 $u,v$ 代表一次事件。

输出格式

共 $q$ 行，对于每个事件回答一行一个答案。

样例 #1

样例输入 #1

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

样例输出 #1

0
50
4294967292
166

样例 #2

样例输入 #2

10 9
2 1
3 2
4 2
5 1
6 5
7 5
8 6
9 7
10 8
24464 5705 28145 23281 16827 9961 491 2995 11942 4827
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9

样例输出 #2

60338
244666
523800
991210
1591884
2152416
2869500
3682634
4577026

提示

本题开启子任务捆绑。

对于 $100 \%$ 的数据，$n,q \leq 2 \times 10^5,a_i < 2^{32}$。