题目描述

在花园中有 $n$ 个花圃，在花圃 $i$，共有 $b_i$ 朵花，这些花属于种类 $s_i$。

此外，还有 $n-1$ 条小径，每条小径连接两花圃 $u_j$ 和 $v_j$（双向）。并且满足小女孩从每一个花圃出发都能到达其它所有花圃。

贾文景邀请了 $d$ 个小女孩，并计划依次让她们从花圃 $1$ 开始采花。每个小女孩有一个目标花圃 $h_k \neq 1$，她们会沿着最短路径到目标花圃，并在经过的每个花圃中采一朵花（包括花圃 $1$）。

每次采花会减少花圃中 $1$ 朵花（如果花的数量不为 $0$）。请帮助贾文景计算每个小女孩过程中采到的花有多少种不同的种类。

输入格式

• 第一行包含两个整数 $n$ 和 $d$，分别表示花圃数量和小女孩数量。

• 第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示每个花圃中花的数量。

• 第三行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$，表示每个花圃花的种类。

• 第四行包含 $d$ 个整数 $h_1, h_2, \dots, h_d$，表示每个小女孩的目标花圃。

• 接下来 $n-1$ 行，每行包含两个整数 $u_j$ 和 $v_j$，表示一条连接花圃 $u_j$ 和 $v_j$ 的小径。

输出格式

输出一行包含 $d$ 个整数，第 $k$ 个整数表示第 $k$ 个小女孩采到的不同种类的数量。

样例 #1

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

2 1 2 1 1 0

样例 #2

7 4
0 2 4 4 0 1 3
6 1 6 2 2 2 1
7 5 2 4
4 1
4 5
6 2
1 6
1 3
6 7

输出 #2

2 1 1 1

说明/提示

【样例解释】

对于样例 $1$，第一个小女孩走到花圃 $2$，采到 $1$ 朵种类 $1$ 的花和 $1$ 朵种类 $2$ 的花。第二个小女孩走到花圃 $5$，采到种类 $1$ 的花，总共采到 $1$ 个种类。

对于样例 $2$，每个小女孩采到的不同种类分别是 $2, 1, 1, 1$。

【数据范围】

• $2 \leq n \leq 2 \times 10^5$
• $1 \leq d \leq 2 \times 10^6$
• $1 \leq s_i \leq n$，$0 \leq b_i \leq d$，$1 \leq u_j, v_j < n$

大数据