题目描述

给定一棵包含 $n$ 个结点的有根树，根结点为 $1$ 号结点，每个结点的权值为 $0$ 或者 $1$。

江桥 认为一条简单路径 $u \rightarrow v$ 是好的，当且仅当 $u \rightarrow v$ 简单路径上的结点权值依次拼接后得到的二进制串所代表的十进制值为 $x$，并且 $\text{lca(u,v)=u or lca(u,v)=v}$，且经过的所有结点的数量不超过 $21$ 个（包括 $u,v$）。

现在给定 $q$ 次询问，每次给定一个整数 $x$，你需要回答树中存在多少条好路径。

注意，$(u,v)$ 的路径和 $(u,v)$ 的路径被视为不同，当且仅当 $u \neq v$。而 $(u,u)$ 也算一条路径。

$\text{lca(u,v)}$: 表示 $u,v$ 两点的最近公共祖先。

输入格式

第一行两个正整数 $n,q$，表示树中的结点数量、询问次数。

接下来一行一个长度为 $n$ 的 $01$ 串 $s$，第 $i$ 个字符表示 $i$ 号结点的权值。

接下来 $n - 1$ 行，每行两个正整数 $u,v$ 表示树中有一条边连接 $u,v$。

接下来 $q$ 行，每行 $1$ 个整数 $x$，表示询问的整数。

输出格式

$q$ 行每行一个非负整数，表示答案。

4 6
0111
1 2
1 3
4 2
0
1
2
3
4
5

1
5
2
3
0
0

样例解释

对于第二组询问 $x = 1$，满足条件的路径有： $(2,2),(3,3),(4,4),(1,2),(1,3)$ 共五条。

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n,q \leq 2 \times 10^{5},1 \leq u_i,v_i \leq n,0 \leq x_i \leq 2^{20},s_{i} \in \{'0','1'\}$。