loj#P6272. 「BestCoder Round #88」Tree Cutting(改)

「BestCoder Round #88」Tree Cutting(改)

题目描述

给一棵 n(1n1000)n(1 \le n \le 1000) 个节点的树,每个点有点权 wi(0wi<215)w_i(0 \le w_i < 2 ^ {15})

fxf_x 表示树上有多少个连通块,满足点权异或和为 xx

f0,f1,f2,...,f2151f_0, f_1, f_2, ..., f_{2 ^ {15} - 1}998244353998244353 取模。

输入格式

第一行一个正整数 nn

第二行 nn 个非负整数 wiw_i

接下来 n1n-1 行,每行两个正整数 x,yx, y ,表示树上存在边 (x,y)(x, y)

输出格式

输出一行,共 2152 ^ {15} 个非负整数,依次为 f0,f1,...,f2151f_0, f_1, ..., f_{2 ^ {15} - 1}

数据范围与提示

对于 100%100\% 的数据,1n1000,0wi<2151 \le n \le 1000, 0 \le w_i < 2 ^ {15}