P11295 [NOISG 2022 Qualification] Dragonfly

在植物园和碧山公园周围的池塘中，经常可以看到蜻蜓。在一个更密集的森林区域中，Benson 记录了 $n$ 个池塘，以及蜻蜓可以捕食的昆虫数量和种类。 在池塘 $i$，共有 $b_i$ 只昆虫，这些昆虫属于种类 $s_i$。 此外，还有 $n-1$ 条小径，每条小径连接两池塘 $u_j$ 和 $v_j$（双向）。并且满足蜻蜓从每一个池塘出发都能到达其它所有池塘。 Benson 抓住了 $d$ 只蜻蜓，并计划依次释放到池塘 $1$。每只蜻蜓有一个目标池塘 $h_k \neq 1$，会沿着最短路径飞到目标池塘，并在经过的每个池塘中捕食昆虫（包括池塘 $1$）。 每次捕食会减少池塘中 $1$ 只昆虫（如果昆虫数量不为 $0$）。需要帮助 Benson 计算每只蜻蜓的飞行过程中捕食到的不同种类昆虫的数量。

请确定每只蜻蜓的飞行过程中捕食到的不同种类昆虫的数量。

- 第一行包含两个整数 $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$，第一只蜻蜓飞向池塘 $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$ | 子任务编号 | 分值 | 额外限制条件 | | :--------: | :--: | :---------------------------------------: | | $1$ | $10$ | $n, d \leq 1000$ | | $2$ | $10$ | $b_i = d$ | | $3$ | $12$ | $b_i \leq 10$ | | $4$ | $12$ | $u_j = j$, $v_j = j + 1$ | | $5$ | $37$ | $s_i = i$ | | $6$ | $16$ | $d \leq 2 \times 10^5$ | | $7$ | $3$ | 无额外限制 |