N - しゃくとり on Namori Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 頂点 N 辺の頂点重み付き単純無向連結グラフ G と正整数 K が与えられます。 i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。 また、 各頂点 i は正整数の重み A_i を持ちます。

以下を満たす G 上の単純パスの最大の辺数を求めて下さい。

  • パス上に現れる（端点を含む）頂点の重みの総積が K 以下
単純パスとは？ 単純パスとは、 G の頂点の列 P = (p_1, p_2, \dots, p_\ell) であって、「任意の 1 \leq i \leq \ell-1 について、 p_i と p_{i+1} は辺で結ばれている」かつ「同じ頂点は二度現れない」ものです。P の辺数は、 \ell-1 として定義されます。

制約

  • 3 \le N \le 2\times 10^5
  • 1 \le K \le 10^9
  • 1 \le A_i \le K
  • 1 \le u_i < v_i \le N
  • 与えられるグラフは単純無向連結
  • 入力はすべて整数

部分点

追加の制約 N \le 5000 を満たすデータセットに正解した場合は 1 点が与えられます。

入力

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

N K
A_1 A_2 \dots A_N
u_1 v_1
u_2 v_2
\vdots
u_N v_N

出力

標準出力へ答えを一行で出力してください。

入力例 1

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

出力例 1

3

辺数 3 の単純パス (5, 2, 3, 6) の頂点重みの総積は 2 \times 2 \times 1 \times 3 = 12 \leq K = 14 です。 一方で、辺数 4 以上の単純パスとその頂点重みの総積は、以下のとおりすべて K より大きいです。

  • (1, 4, 3, 2, 5) とその逆 : 36
  • (2, 1, 4, 3, 6) とその逆 : 54
  • (3, 4, 1, 2, 5) とその逆 : 36
  • (4, 1, 2, 3, 6) とその逆 : 54
  • (5, 2, 1, 4, 3, 6) とその逆 : 108

入力例 2

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

出力例 2

5

単純パス (5, 2, 1, 4, 3, 6) の頂点重みの総積は 108 = K であり、これより辺数の大きい単純パスはありません。

入力例 3

6 128
78 85 80 67 20 24
1 2
2 3
3 4
1 4
2 5
3 6

出力例 3

0

この入力例において、 2 頂点以上からなる単純パスの頂点の重みの総積は K より大きくなります。 したがって、 1 頂点のみからなるパス、たとえば (1) が辺数 0 で最大となります。