配点 : 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 是最大值。