Dragonfly

Dragonflies can be seen around ponds at Botanic Gardens and Bishan Park. In one of the denser forested areas, Benson the Rabbit has noted down $n$ ponds that the dragonflies fly around. Pond $i$ ($1 ≤ i ≤ n$) has $b_i$ bugs that the dragonflies can eat. The bugs at pond $i$ belong to species $s_i$.

Benson has also noted down $n-1$ trails. Trail $j$ ($1 ≤ j < n$) connects two distinct ponds $u_j$ and $v_j$ in both directions. Dragonflies can travel from any pond to any other pond using only the trails.

Benson has captured $d$ dragonflies and intends to release them one at a time at pond $1$. Dragonfly $k$ ($1 ≤ k ≤ d$) has a home pond $h_k \ne 1$ and travels to pond $h_k$ without visiting any pond more than once, using only the trails. The dragonflies are released in increasing order, from dragonfly $1$ to dragonfly $d$. After a dragonfly is released, it eats one bug at every pond it visits, including pond $1$. The count at each of those ponds drops by $1$ if it is not $0$.

Help Benson determine the number of distinct species of bugs eaten by each dragonfly during its journey.

The first line contains two space-separated integers $n$ and $d$. The next line contains $n$ space-separated integers $b_1, b_2, \cdots, b_n$. The next line contains $n$ space-separated integers $s_1, s_2, \cdots, s_n$. The next line contains $d$ space-separated integers $h_1, h_2, \cdots, h_d$. Each of the next $n-1$ lines contains two space-separated integers, where the $i$th of these lines contains $u_i$ and $v_i$.

Output a single line with $d$ space-separated integers. The $k$th integer is the number of distinct species of bugs eaten by dragonfly $k$.

• $2 ≤ n ≤ 2 \cdot 10^5$
• $1 ≤ d ≤ 2 \cdot 10^6$
• $1 ≤ s_i ≤ n$ (for all $1 ≤ i ≤ n$)
• $0 ≤ b_i ≤ d$ (for each $1 ≤ i ≤ n$)
• $1 ≤ u_j, v_j ≤ n$, $u_j \ne v_j$ (for each $1 ≤ j ≤ n-1$)
• $2 ≤ h_k ≤ n$ (for each $1 ≤ k ≤ n$)