006 - Colorful Tree

問題

$N \ $頂点$ \ N - 1 \ $辺のグラフがあります。このグラフは木です。
各頂点色が塗られており、頂点$ \ i \ (1 \leq i \leq N) \ $は色$ \ C_i \ $で塗られています。また、各辺は異なる2頂点を双方向に結び、$i \ (1 \leq i \leq N - 1) \ $番目の辺は頂点$ \ u_i,v_i \ $間を結びます。

以下のようなクエリが$ \ Q \ $回にわたって与えられます。順に処理してください。

• 頂点$ \ x_i \ $の色を$ \ c_i \ $に変更し、頂点$ \ x_i \ $に直接繋がっている頂点の色は何種類あるか出力する。

入力

入力は以下の形式で標準入力から与えられる。

$N \ Q$
$C_1 \ C_2 \ \ldots \ C_N$
$u_1 \ v_1$
$u_2 \ v_2$
$\vdots$
$u_{N - 1} \ v_{N - 1}$
$x_1 \ c_1$
$x_2 \ c_2$
$\vdots$
$x_Q \ c_Q$

出力

各クエリについて、色の種類数を改行区切りで出力せよ。

制約

全ての入出力ケースについて以下を満たす。

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 5 \times 10^5$
• $1 \leq C_i \leq 10^9$
• $1 \leq u_i,v_i \leq N$
• $1 \leq x_i \leq N$
• $1 \leq c_i \leq 10^9$
• 与えられるグラフは木である
• 入力は全て整数

入出力例

入力例

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

出力例

4
1
3

各クエリで以下のような処理が行われます

• クエリ1: 頂点$ \ 2 \ $の色が$ \ 1 \ $に変更され、頂点$ \ 2 \ $と直接繋がっている頂点は頂点$ \ 1,3,4,5 \ $であり、色は$ \ 1,3,4,2 \ $なので$ \ 4 \ $を出力する。
• クエリ2: 頂点$ \ 1 \ $の色が$ \ 4 \ $に変更され、頂点$ \ 1 \ $と直接繋がっている頂点は頂点$ \ 2,6 \ $であり、色は$ \ 1,1 \ $なので$ \ 1 \ $を出力する。
• クエリ3: 頂点$ \ 2 \ $の色が$ \ 2 \ $に変更され、頂点$ \ 2 \ $と直接繋がっている頂点は頂点$ \ 1,3,4,5 \ $であり、色は$ \ 4,3,4,2 \ $なので$ \ 3 \ $を出力する。