問題一覧 > 通常問題

No.2634 Tree Distance 3

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 : ebi_flyebi_fly / テスター : noya2noya2 👑 potato167potato167
5 ProblemId : 10661 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-16 19:34:30

問題文

頂点に 11 から NN までの番号がついた NN 頂点の木 TT が与えられます。 ii 番目の辺は頂点 uiu_i と頂点 viv_i を結んでいます。また、頂点 ii には AiA_i が書かれています。 i=1,2,,Ni = 1,2,\dots,N について以下の問題を解いてください。

  • AiAjA_i \leq A_j である jj ( 1jN1\leq j \leq N) のうち木 TT での 22 頂点 ii, jj の距離 d(i,j)d(i, j) の最大値を求めてください。

ここで、木の 22 頂点 ii, jj の距離 d(i,j)d(i, j) とは、 iijj を両端点とするパスに含まれる辺の本数です。

制約

  • 2N2×1052 \leq N \leq 2\times 10^5
  • 0Ai1090 \leq A_i \leq 10^9
  • 1ui,viN1 \leq u_i, v_i \leq N
  • 入力で与えられるグラフは木である
  • 入力はすべて整数である

入力

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

NN
A1A_1 A2A_2 \dots ANA_N
u1u_1 v1v_1
u2u_2 v2v_2
\vdots
uN1u_{N-1} vN1v_{N-1}

出力

i=1,2,,Ni = 1,2,\dots,N に対して、答えを空白区切りで出力せよ。

サンプル

サンプル1
入力
5
4 2 2 3 1
1 2
1 3
3 4
3 5
出力
0 3 2 2 3

i=1i = 1 について、 jj としてとる値は 11 のみなので答えは 00 です。

i=2i = 2 について、 jj としてとる値は 11, 22, 33, 44 であり、答えは j=4j = 4 の場合で 33 です。

i=3i = 3 について、jj としてとる値は 11, 22, 33, 44 であり、答えは j=2j = 2 の場合で 22 です。

i=4i = 4 について、 jj としてとる値は 11, 44 であり、答えは j=1j = 1 の場合で 22 です。

i=5i = 5 について、 jj としてとる値は 11, 22, 33, 44, 55 であり、答えは j=2j = 2 の場合で 33 です。

サンプル2
入力
6
2 9 1 4 6 8
1 2
1 3
1 4
3 5
3 6
出力
2 0 2 3 3 3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。