#YDRG007E. 广义串并联图上邻域数点

广义串并联图上邻域数点

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

题目描述

有一棵 nn 个点的树与 nn 个集合 SiS_i,初始时 Si={i}S_i = \{i\},树上每个节点有一个权值 aia_i

对于一个集合 SS 与两个节点 u,vu,v 而言,令 t=0t = 0,然后依次遍历树上 uuvv 的简单路径经过的节点。假若遍历到的节点 iSi \in S ,那么让 tt+ait \gets t + a_i ,否则让 ttait \gets t - a_i。其中 \leftarrow 表示赋值。将最后抵达节点 vvtt 的值定义为 cost(S,u,v)\text{cost}(S,u,v)(此时节点 vvtt 的改变已经完成),再定义一个集合的权值 $\text{val}(S) = \sum_{u \in S} \sum_{v \in {S \setminus u}} \text{cost}(S,u,v)$。

现在有 qq 次事件。每次事件形如 u,v ,表示令 SuSuSvS_u \gets S_u \cup S_v 并删除集合 SvS_v

事件结束后,你需要回答 val(Su)\text{val}(S_u)2322^{32} 取模后的值,保证事件开始前集合 Su,SvS_u,S_v 均未被删除。

输入格式

11 行共两个数 n,qn,q

2 n2~n 行,每行两个数 u,vu,v 代表树上一条边。

n+1n + 1 行共 nn 个数,分别表示 a1ana_1\sim a_n

n+2n+q+1n + 2 \sim n + q + 1 行,共 qq 行,每行两个数 u,v 代表一次事件。

输出格式

qq 行,表示对于每个事件回答,一行一个答案。

样例 #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

提示

本题开启子任务捆绑。

子任务编号 特殊性质 分值
11 n,q103n,q \leq 10^3 2020
22 n,q4×104n,q \leq 4 \times 10^4 3535
33 对于任意 1in1 \leq i \leq n 满足 ai=231a_i = 2^{31} 55
44 对于任意 1in1 \leq i \leq n 保证满足 ai0a_i \not = 0ii 至多有 1010 2020
55 无特殊性质

对于 100%100 \% 的数据,n,q2×105,ai<232n,q \leq 2 \times 10^5,a_i < 2^{32}