AT_nupc2024_n しゃくとり on Namori

给定一个有 $N$ 个顶点和 $N$ 条边的顶点带权重的简单无向连通图 $G$，以及一个正整数 $K$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。每个顶点 $i$ 具有一个正整数权重 $A_i$。 请你求出满足以下条件的 $G$ 上的简单路径的最大边数： - 路径上出现的所有顶点（包括端点）的权重之积不超过 $K$。 什么是简单路径？简单路径是指一列顶点 $P = (p_1, p_2, \dots, p_\ell)$，满足对于任意 $1 \leq i \leq \ell-1$，$p_i$ 和 $p_{i+1}$ 之间有一条边连接，且同一顶点不会出现两次。$P$ 的边数定义为 $\ell-1$。

输入以如下格式通过标准输入给出。 > $N \ K\ A_1\ A_2\ \dots\ A_N\ u_1\ v_1\ u_2\ v_2\ \vdots\ u_N\ v_N$

请将答案输出一行。

## 部分分 对于满足额外限制 $N \le 5000$ 的数据集，正确解答可以获得 $1$ 分。 ## 样例解释 1 边数为 $3$ 的简单路径 $(5, 2, 3, 6)$ 的顶点权重之积为 $2 \times 2 \times 1 \times 3 = 12 \leq K = 14$。而其他边数大于 $3$ 的简单路径及其顶点权重之积如下： - $(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$ 这些都大于 $K$。 ## 样例解释 2 简单路径 $(5, 2, 1, 4, 3, 6)$ 的顶点权重之积为 $108 = K$，没有边数更大的路径。 ## 样例解释 3 在这个输入样例中，任意包含 $2$ 个及以上顶点的简单路径的顶点权重之积都会超过 $K$。因此，仅包含单个顶点的路径，比如 $(1)$，其边数为 $0$，也是最大的。 # 数据范围与约定 - $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$ - 所给图为简单无向连通图 - 所有输入均为整数。 由 ChatGPT 5 翻译