0362 - 同期 (Synchronization)

時間制限 2 秒 / メモリ制限 512 MB / 得点 100 / Writer root / x 0 / 統計 /

TLE
2sec
MLE
512MB
得点
100

問題

　JOI 社は，世界中に全部で N 台のサーバーを置いている．それぞれのサーバーには 1 つの互いに異なる重要な情報が含まれている．JOI 社は，サーバー間に回線を敷設して，情報をサーバー間で共有することにした．2 つのサーバーの間に回線が敷設されると，それらのサーバー間では情報をやりとりできるようになる．また，あるサーバーから，敷設されている回線をいくつか経由して到達できるような他のサーバーとの間でも情報をやりとりできる．
　サーバーには高性能な同期システムが搭載されており，ある 2 つのサーバーが互いに情報をやりとりでき，かつそれらのサーバーの持っている情報が異なるときには自動的に同期が行われる．サーバー A, B の間で同期が行われると，A, B の持つ情報は同期前に A, B の少なくとも片方が持っていた情報すべてになる．費用を抑えるため，敷設できる回線は N - 1 箇所に限られている．それらすべての回線が敷設されたとき，各サーバーから他のすべてのサーバーまで，同じサーバーを 2 回以上通らずに情報を伝える方法がちょうど 1 通り存在するようになっている．
　最初（時刻 0）はどの回線も敷設されていない．また，回線が敷設される場所には，極めて過酷な条件(砂漠，海底など) もあるため，回線が使用不能になることも多い．使用不能になった回線は，その後再び敷設されるまで利用することはできない．
　今，時刻 j (1 ≤ j ≤ M) において，ちょうど 1 つの回線の状態が変化したことがわかっている．このとき，いくつかのサーバーについて，時刻 M + 1 において持っている異なる情報が何種類あるかを知りたい．

課題

　敷設できる回線および回線の敷設状況が与えられたとき，いくつかのサーバーについて，持っている異なる情報は何種類あるか求めるプログラムを作成せよ．

入力

　標準入力から以下の入力を読み込め．

  • 1 行目には整数 N, M, Q がこの順に空白を区切りとして書かれている．これは，サーバーの台数が N であり，回線の敷設状況の情報が M 個あり，持っている情報の種類を求めたいサーバーが Q 台あることを意味する．
  • 続く N - 1 行のうち i 行目 (1 ≤ i ≤ N - 1) には整数 Xi, Yi が空白を区切りとして書かれている．これは，回線 i が敷設されたときにサーバー Xi, Yi をつなぐことを表す．
  • 続く M 行のうち j 行目 (1 ≤ j ≤ M) には整数 Dj が書かれている．これは，時刻 j に回線 Dj の敷設状況が変化したことを表す．つまり，時刻 j になる直前に回線 Dj が敷設されていなければ新たに敷設され，敷設されていれば使用不能になったことを表す．時刻 j に敷設状況の変化があった後，時刻 j + 1 までに同期はすべて完了するものとする．
  • 続く Q 行のうち k 行目 (1 ≤ k ≤ Q) には整数 Ck が書かれている．これは，最終的にサーバー Ck が何種類の情報を持っているか求めたいということを表す．

出力

　標準出力に Q 行出力せよ．k 行目 (1 ≤ k ≤ Q) には，サーバー Ck が最終的に持っている情報の種類数を表す 1 つの整数を出力せよ．

制限

　すべての入力データは以下の条件を満たす.

  • 2 ≤ N ≤ 100 000．
  • 1 ≤ M ≤ 200 000．
  • 1 ≤ Q ≤ N．
  • 1 ≤ Xi ≤ N, 1 ≤ Yi ≤ N, Xi ≠ Yi (1 ≤ i ≤ N - 1)．
  • 1 ≤ Dj ≤ N - 1 (1 ≤ j ≤ M)．
  • 1 ≤ Ck ≤ N (1 ≤ k ≤ Q)．
  • Ck の値は互いに異なる．
  • 回線がすべて敷設されたとすると，どの異なる 2 つのサーバー間も 1 つ以上の回線を経由して通信することができる．

小課題

小課題 1 [30 点]

  • Q = 1 を満たす．

小課題 2 [30 点]

  • Xi = i, Yi = i + 1 (1 ≤ i ≤ N - 1) を満たす．

小課題 3 [40 点]

　追加の制限はない．

入出力例

入力例 1

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

出力例 1

3
5
4

　最初サーバー i (1 ≤ i ≤ 5) が持っている情報の番号を i とする．この例では，

  • 時刻 1 において，回線 1 が敷設され，サーバー 1, 2 がつながれる．そして，サーバー 1, 2 の持っている情報がいずれも 1, 2 になる．
  • 時刻 2 において，回線 2 が敷設され，サーバー 1, 3 がつながれる．回線 1 を含めるとサーバー 1, 2, 3 が回線で結ばれることになり，サーバー 1, 2, 3 の持っている情報がいずれも 1, 2, 3 になる．
  • 時刻 3 において，回線 1 はすでに敷設されているので，使用不能になる．
  • 時刻 4 において，回線 4 が敷設され，サーバー 2, 5 がつながれる．そして，サーバー 2, 5 の持っている情報がいずれも 1, 2, 3, 5 になる．ここで，サーバー 1, 2 の間は回線 1 が使用不能になったことより通信ができないことに注意せよ．
  • 時刻 5 において，回線 4 が使用不能になる．
  • 時刻 6 において，回線 3 が敷設され，サーバー 2, 4 がつながれる．そして，サーバー 2, 4 の持っている情報がいずれも 1, 2, 3, 4, 5 になる．

以上の通り，最終的にサーバー 1, 4, 5 が持っている情報の種類数はそれぞれ 3, 5, 4 となる．