#P17746. 校庆

校庆

题目描述

风景怡人的华懿高级中学一共有n 个景点,有n-1 条道路将其连接。游客参观第i 个景点时会收获wiw_{i}愉悦度。但是如果多次参观类似的景点会令人心生厌烦,所以总共获得的愉悦度为:所有选择的景点的愉悦度的异或和。

由于正值华懿高级中学70 周年校庆,所以每一天都会翻新一条从x 到y 的路径上的所有景点,此时这些景点将不能被访问。为了安排参观,现在主办方想知道:在剩下的所有景点中,有多少种选择方案能够使得总愉悦度为k。

为了避免给你带来太多困扰,主办方只需要对998244353 取模后的结果。你能够帮帮他吗?

输入格式

从标准输入读入。

第一行两个整数n,m,表示景点数和询问数。

接下来n-1 行,每一行两个数x,y,表示原图的一条边(x,y)。

接下来一行n 个数,第i 个数表示i 号景点的愉悦度为wiw_{i}。

接下来m 行,每行三个数x,y,k,表示原图的(x,y)这条路径正在整修,主办方想知道有多少种选择方法使得异或值为k。

输出格式

输出到标准输出。

一共输出m 行,第i 行表示第i 组询问的答案。

输入样例

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

输出样例

1
2
2

样例解释

对于第一天,删去2->3 这条路径上的景点后,剩下景点为4、5;

其中选择(5)可以使得愉悦度为2.

对于第二天,删去1->1 这条路径上的景点后,剩下景点为2、3、

4、5;其中选择(4)、(2,5)可以使得愉悦度为4.

对于第三天,删去4->4 这条路径上的景点后,剩下景点为1、2、

3、5;其中选择(5)、(1,3)可以使得愉悦度为2.

数据约定

对于10%的数据,有n,m≤5。

对于30%的数据,有n,m≤1000。

对于60%的数据,有n,m≤50000。

另有20%的数据,保证询问时x 为y 的祖先。

对于100%的数据,1≤n,m≤200000,0≤wiw_{i},k≤32767.