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

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

Score: 100 points

Problem Statement

There are N towns in the country of IOI where JOI-kun lives, numbered from 1 to N. Also, there are N-1 roads in the country of IOI, numbered from 1 to N-1. Road j (1 \leq j \leq N-1) connects town U_j and town V_j in both directions. It is possible to travel from any town to any other town by using some number of roads.

A stamp rally will now be held in the country of IOI. One stamp station will be installed in each town. The stamp station in town i (1 \leq i \leq N) will be installed at time T_i.

JOI-kun decides to participate in the stamp rally. At time 0, JOI-kun starts from one of the towns. Also, JOI-kun has stamina D at time 0.

When JOI-kun is in town i at time t, he takes the following actions.

  1. First, if a stamp station has already been installed in the current town, he presses the stamp. That is, he presses the stamp if T_i \leq t.
  2. Next, he chooses either to finish the stamp rally or to move to another town. However, he can choose to move to another town only if there exists an adjacent town connected to town i by a road that he has not visited yet, and his current stamina is at least 1.
  3. If JOI-kun chooses to move to another town, he chooses an unvisited town j among the towns connected to town i by a road, and moves there. His stamina decreases by 1, and he arrives at town j at time t+1.
  4. If JOI-kun chooses to finish the stamp rally, the rally is successful if he has pressed a stamp at least once up to that point, and he can receive a present there. Otherwise, the rally is unsuccessful.

Assume that all times other than travel time between towns are negligible. Note that JOI-kun cannot stay in the same town.

You are an event organizer. If JOI-kun succeeds in the stamp rally, you need to prepare presents in the corresponding towns. However, the number of presents is limited, so you want to prepare presents in as few towns as possible. Unfortunately, you do not know from which town JOI-kun will start. Therefore, for each s (1 \leq s \leq N), you want to find the number of towns in which presents must be prepared when JOI-kun starts from town s. In other words, you need to count the number of g (1 \leq g \leq N) such that it is possible for the stamp rally to be successful when JOI-kun finishes at town g.

Given the information about the towns and roads in the country of IOI, JOI-kun's stamina, and the installation times of the stamp stations, write a program that computes, for each town, the number of towns in which presents must be prepared when JOI-kun starts from that town.

Input

Read the following data from the standard input.

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

Output

Write N lines to the standard output. The s-th line (1\leq s \leq N) should contain the number of towns in which presents must be prepared when JOI-kun starts from town s.

Constraints

  • 2 \leq N \leq 400\,000.
  • 0 \leq D \leq N-1.
  • 0 \leq T_i \leq N (1 \leq i \leq N).
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq N-1).
  • It is possible to travel from any town to any other town by using some number of roads.
  • Given values are all integers.

Subtasks

  1. (3 points) D\leq 1.
  2. (7 points) N\leq 3\,000, (U_j,V_j)=(j,j+1) (1\leq j \leq N-1).
  3. (10 points) N\leq 3\,000.
  4. (11 points) (U_j,V_j)=(j,j+1) (1\leq j \leq N-1).
  5. (41 points) D=N-1, N \leq 150\,000.
  6. (28 points) No additional constraints.

Sample Input 1

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

Sample Output 1

2
3
4
2
2

We show one example of JOI-kun's actions when s=1.

  • At time 0, JOI-kun is in town 1 and takes the following actions.
    • The stamp station in town 1 has not been installed yet, so JOI-kun does not press a stamp.
    • JOI-kun's current stamina is 2. He moves to town 2, which is one of the unvisited towns connected to town 1 by a road.
    • JOI-kun's stamina decreases by 1, and he arrives at town 2 at time 1.
  • At time 1, JOI-kun is in town 2 and takes the following actions.
    • The stamp station in town 2 has not been installed yet, so JOI-kun does not press a stamp.
    • JOI-kun's current stamina is 1. He moves to town 3, which is one of the unvisited towns connected to town 2 by a road.
    • JOI-kun's stamina decreases by 1, and he arrives at town 3 at time 2.
  • At time 2, JOI-kun is in town 3 and takes the following actions.
    • The stamp station in town 3 has already been installed, so JOI-kun presses a stamp.
    • JOI-kun chooses to finish the stamp rally here. Since he has pressed a stamp at least once, the stamp rally is successful. He receives a present there.

Therefore, when JOI-kun starts from town 1 and finishes the stamp rally at town 3, the stamp rally can be successful, so it is necessary to prepare a present in town 3. When JOI-kun starts from town 1, presents must be prepared only in towns 3 and 4, so the first line of the output should be 2.

Also, when JOI-kun starts from town 2, presents must be prepared only in towns 3, 4, and 5, so the second line of the output should be 3.

This input example satisfies the constraints of subtasks 3,6.

Sample Input 2

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

Sample Output 2

2
1
2
0
1

This input example satisfies the constraints of subtasks 1,2,3,4,6.

Sample Input 3

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

Sample Output 3

2
2
7
5
1
2
5

This input example satisfies the constraints of subtasks 3,5,6.

配点： 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. (3 点) D\leqq 1．
  2. (7 点) N\leqq 3\,000，(U_j,V_j)=(j,j+1) (1\leqq j \leqq N-1)．
  3. (10 点) N\leqq 3\,000．
  4. (11 点) (U_j,V_j)=(j,j+1) (1\leqq j \leqq N-1)．
  5. (41 点) D=N-1，N \leqq 150\,000．
  6. (28 点) 追加の制約はない．

入力例 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 の制約を満たす．