题目描述

由乃不太会打扑克，所以她出了一个数据结构题。

给一个 $n$ 个点树，第 $i$ 个点的点权为 $a_i$，$m$ 次操作， 每次求一些树链的并的贡献，强制在线。

贡献定义：

定义权值集合为这些树链的并里面出现过的所有点权的集合。

权值集合中每一段连续出现的数的贡献为这一段长度的k次方。

例如出现了 $1,9,2,6,0,8,1,7$ 这些数，$k=3$ 的时候贡献为 $3^3+4^3$，因为 $0,1,2$ 是连续一段，$6,7,8,9$ 为连续一段。

每次询问给出 $x$ 条树链，以及一个 $k$，贡献对 $2^{32}$ 取模。

输入格式

一行两个整数 $n,m$。
接下来一行 $n$ 个整数， 第 $i$ 个整数表示 $a_i$。
接下来 $n -1$ 行每行两个数 $u,v$， 用来描述树上的一条边。
接下来 $m$ 行， 每行首先给出一个数 $x$， 接下来 $2x$ 个数， 读入的这 $2x$ 个数需要异或上一次询问的答案解密得到，初始答案为 $0$， 得到的第 $2i+1$ 以及 $2i+2$ 个数表示第 $i$ 条链的起点以及终点， 最后一个数 $k$。

输出格式

对于每个询问输出一个数表示答案。

8 2
1 9 2 6 0 8 1 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2 1 4 5 8 3
1 90 90 2

91
1

数据范围与约定

对于 $100\%$ 的数据，$0\le n ,m\le 10^5$，$0\le \sum x\le 10^5$，$0\le k\le 30$， $0\le a_i\le 3\times 10^4$，$1\le u,v\le n$。

题目来源

By 佚名提供