8812: BZOJ4812: [Ynoi2017]由乃打扑克
Memory Limit:666 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
由乃不太会打扑克 所以她出了一个数据结构题 给一个N个点树,第i个点的点权为Ai,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个整数表示Ai 接下来N-1行每行两个数u,v, 用来描述树上的一条边, 1≤u,v≤N 接下来M行, 每行首先给出一个数x, 接下来2x个数, 读入的这2x个数需要异或上一次询问的答案解密得到,初 始答案为0, 得到的第2i+1以及2i+2个数表示第i条链的起点以及终点, 最后一个数k 0≤N,M≤10^5, 0≤∑x≤10^5, 0≤k≤30, 0≤Ai≤30000
输出格式
对于每个询问输出一个数表示答案
样例输入
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
提示
没有写明提示
题目来源
By 佚名提供