H - スタンプラリー 5 (Collecting Stamps 5) 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

JOI 君が住む IOI 国には N 個の街があり，1 から N までの番号が付けられている． また，IOI 国には N-1 本の道路があり，1 から N-1 までの番号が付けられている． 道路 j (1 \leqq j \leqq N-1) は街 U_j と街 V_j を双方向に結んでいる． どの街からどの街へも何本かの道路を通ることによって移動することができる．

これから IOI 国でスタンプラリーが開催される． それぞれの街には 1 つのスタンプ台が設置される予定である． 街 i (1 \leqq i \leqq N) のスタンプ台は時刻 T_i に設置される．

JOI 君はスタンプラリーに参加することにした． JOI 君は時刻 0 にいずれかの街から行動を開始する． また，JOI 君は時刻 0 の時点で体力が D である．

JOI 君は時刻 t に街 i にいるとき，次の行動をとる．

  1. まず，現在いる街に既にスタンプ台が設置されている場合はスタンプを押す． すなわち，T_i \leqq t の場合はスタンプを押す．
  2. 次に，スタンプラリーを終了するか別の街に移動するかを選ぶ． ただし，街 i と道路で結ばれた街で，まだ訪れたことのない街が存在し，かつ，現在の体力が 1 以上であるときに限り，別の街に移動することを選ぶことができる．
  3. JOI 君が別の街に移動することを選んだ場合，JOI 君は街 i と道路で結ばれた街のうち，まだ訪れたことのない街 j を選び，移動する． 体力が 1 減少し，時刻 t+1 に街 j に到着する．
  4. JOI 君がスタンプラリーを終了することを選んだ場合，それまでに一度以上スタンプを押した場合はスタンプラリー成功となり，その場でプレゼントを受け取ることができる．そうでない場合はスタンプラリー失敗となる．

街の移動にかかる時間以外は無視できるものとする． JOI 君が同じ街に留まることはできないことに注意せよ．

大会の運営者であるあなたは，JOI 君がスタンプラリーに成功した場合のためにそれぞれの街にプレゼントを用意しておく必要があるが，プレゼントの数には限りがあるため，必要最小限の街にプレゼントを用意したい． しかしながら，あなたは JOI 君がどの街から行動を開始するかについての情報を持っていない． そこで，あなたはそれぞれの s (1 \leqq s \leqq N) について，JOI 君が街 s から行動を開始したときに，プレゼントを用意しておく必要のある街の数，すなわち，JOI 君が街 g でスタンプラリーを終了をしたときにスタンプラリー成功となる可能性があるような g (1\leqq g\leqq N) の数を求めたい．

IOI 国の街と道路の情報，JOI 君の体力，およびスタンプ台の設置時刻が与えられたとき，それぞれの街について， その街から JOI 君が行動を開始したときにプレゼントを用意しておく必要のある街の数を求めるプログラムを作成せよ．

入力

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

N D
T_1 T_2 \cdots T_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

標準出力に，N 行出力せよ． s 行目 (1\leqq s \leqq N) には，JOI 君が街 s から行動を開始したときにプレゼントを用意しておく必要のある街の数を出力せよ．

制約

  • 2 \leqq N \leqq 400\,000．
  • 0 \leqq D \leqq N-1．
  • 0 \leqq T_i \leqq N (1 \leqq i \leqq N)．
  • 1 \leqq U_j < V_j \leqq N (1 \leqq j \leqq N-1)．
  • どの街からどの街へも何本かの道路を通ることによって移動することができる．
  • 入力される値はすべて整数である．

小課題

  1. (5 点) D\leqq 1．
  2. (9 点) N\leqq 3\,000，(U_j,V_j)=(j,j+1) (1\leqq j \leqq N-1)．
  3. (17 点) N\leqq 3\,000．
  4. (17 点) (U_j,V_j)=(j,j+1) (1\leqq j \leqq N-1)．
  5. (33 点) D=N-1，N \leqq 150\,000．
  6. (19 点) 追加の制約はない．

入力例 1

5 2
2 2 0 1 3
1 2
2 3
2 4
4 5

出力例 1

2
3
4
2
2

s=1 のとき，JOI 君の行動の一例を示す．

  • JOI 君は時刻 0 に街 1 にいる状態で，次の行動をとる．
    • 街 1 にはまだスタンプ台が設置されていないため，JOI 君はスタンプを押さない．
    • JOI 君の現在の体力は 2 である．街 1 と道路で結ばれた街のうち，まだ訪れたことのない街の一つである街 2 に移動する．
    • JOI 君の体力が 1 減少し，時刻 1 に街 2 に到着する．
  • JOI 君は時刻 1 に街 2 にいる状態で，次の行動をとる．
    • 街 2 にはまだスタンプ台が設置されていないため，JOI 君はスタンプを押さない．
    • JOI 君の現在の体力は 1 である．街 2 と道路で結ばれた街のうち，まだ訪れたことのない街の一つである街 3 に移動する．
    • JOI 君の体力が 1 減少し，時刻 2 に街 3 に到着する．
  • JOI 君は時刻 2 に街 3 にいる状態で，次の行動をとる．
    • 街 3 には既にスタンプ台が設置されているため，JOI 君はスタンプを押す．
    • JOI 君はここでスタンプラリーを終了することを選ぶ．これまでに一度以上スタンプを押しているため，スタンプラリー成功となる．その場でプレゼントを受け取る．

よって，JOI 君が街 1 から行動を開始し，街 3 でスタンプラリーを終了したときにスタンプラリー成功となる可能性があるため，街 3 にプレゼントを用意しておく必要がある． JOI 君が街 1 から行動を開始したときにプレゼントを用意しておく必要のある街は街 3 と街 4 のみであるため，1 行目には 2 を出力する．

また，JOI 君が街 2 から行動を開始したときにプレゼントを用意しておく必要のある街は街 3，街 4 と街 5 のみであるため，2 行目には 3 を出力する．

この入力例は小課題 3,6 の制約を満たす．

入力例 2

5 1
0 1 2 1 2
1 2
2 3
3 4
4 5

出力例 2

2
1
2
0
1

この入力例は小課題 1,2,3,4,6 の制約を満たす．

入力例 3

7 6
2 3 0 4 1 3 4
1 2
2 3
2 4
1 5
1 6
6 7

出力例 3

2
2
7
5
1
2
5

この入力例は小課題 3,5,6 の制約を満たす．