잠자리

잠자리는 보타닉 가든과 비산공원 주변의 연못에서 볼 수 있다. 숲이 빽빽한 지역에서 토끼 벤슨은 잠자리가 날아다니는 연못 $n$개를 기록했다. 연못 $i$ ($1 ≤ i ≤ n$)에는 잠자리가 먹을 수 있는 벌레 $b_i$마리가 있다. 연못 $i$의 벌레는 종 $s_i$에 속한다.

벤슨은 길 $n-1$개도 기록했다. 길 $j$ ($1 ≤ j < n$)는 서로 다른 연못 $u_j$와 $v_j$를 양방향으로 잇는다. 잠자리는 길만 이용해 어떤 연못에서든 다른 모든 연못으로 갈 수 있다.

벤슨은 잠자리 $d$마리를 잡았고, 연못 $1$에서 한 마리씩 풀어 주려 한다. 잠자리 $k$ ($1 ≤ k ≤ d$)의 집은 연못 $h_k \ne 1$이며, 같은 연못을 두 번 방문하지 않고 길만 이용해 $h_k$까지 이동한다. 잠자리는 1번부터 $d$번까지 순서대로 풀려난다. 풀려난 잠자리는 방문하는 모든 연못(연못 1 포함)에서 벌레를 한 마리씩 먹는다. 벌레가 남아 있는 연못은 벌레 수가 1 줄고, 0인 연못은 그대로 둔다.

벤슨을 도와 각 잠자리가 여행 중에 먹은 벌레의 서로 다른 종 수를 구하라.

첫 줄에는 공백으로 구분된 정수 $n$과 $d$가 주어진다. 다음 줄에는 공백으로 구분된 정수 $b_1, b_2, \cdots, b_n$이 주어진다. 다음 줄에는 $s_1, s_2, \cdots, s_n$이, 그다음 줄에는 $h_1, h_2, \cdots, h_d$가 주어진다. 다음 $n-1$개 줄의 $i$번째 줄에는 정수 $u_i$와 $v_i$가 주어진다.

공백으로 구분된 정수 $d$개를 한 줄에 출력한다. $k$번째 정수는 잠자리 $k$가 먹은 벌레의 서로 다른 종 수이다.

• $2 ≤ n ≤ 2 \cdot 10^5$
• $1 ≤ d ≤ 2 \cdot 10^6$
• $1 ≤ s_i ≤ n$ (모든 $1 ≤ i ≤ n$에 대해)
• $0 ≤ b_i ≤ d$ (각 $1 ≤ i ≤ n$에 대해)
• $1 ≤ u_j, v_j ≤ n$, $u_j \ne v_j$ (각 $1 ≤ j ≤ n-1$에 대해)
• $2 ≤ h_k ≤ n$ (각 $1 ≤ k ≤ n$에 대해)