問題
$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 \ $を出力する。