\(P = \prod A\) とします。

\(P > M\) なら答えは No です。

以降 \(1 \leq P \leq M\) として、スコアの総和の最小値を求めます。

結論から言うと、パスグラフであって、頂点を左右一列に並べたときにから左から \(i\) 番目の頂点を \(x_i\) としたとき、\(A_{x_1} \geq A_{x_2} \geq \dots \geq A_{x_i} \leq A_{x_{i+1}} \leq \dots \leq A_{x_N}\) （※ 1）であるものの一つが条件を満たします。

\(P \leq M \leq 10^{18}\) より、上記の条件を満たすものは少ないです。
そのため全探索してスコアの総和が \(M\) 以下のものがあればそれを出力し、なければ No とすればよいです。

パスグラフになることの証明

\(A\) を並び替えてもスコアの総和には影響しないので、都度適当に並び替えてもよいことにします。
また \(P\) のスコアの総和への寄与はグラフによって変わらないので、ちょうど \(1\) 本の辺を削除したときのスコアの総和の最小値を求めるとしてよいです。（以降、スコアの総和といったときはこちらを指すものとします。）

まず頂点数が \(4\) の木に対して、スコアの総和の最小値を取る木がスターグラフしかないという状況が存在しないことを示します。

頂点 \(1,2,3\) がこの順にパスグラフを成し、頂点 \(4\) が \(3\) つの頂点のいずれかと隣接している \(3\) つのグラフを考えます。このとき、それぞれのスコアの総和は以下となります。

• \(1\) と \(4\) が隣接: \(A_3 + A_4 + A_1A_4 + A_2A_3 + A_1A_2A_3 + A_1A_2A_4\)
• \(2\) と \(4\) が隣接（スターグラフ）: \(A_1 + A_3 + A_4 + A_1A_2A_3 + A_1A_2A_4 + A_2A_3A_4\)
• \(3\) と \(4\) が隣接: \(A_1 + A_4 + A_1A_2 + A_3A_4 + A_1A_2A_3 + A_2A_3A_4\)

さて、スターグラフのスコアの総和が単独で最小となる場合は \((A_1A_2 - A_3)(A_4-1) < 0\) と \((A_3A_2 - A_1)(A_4-1) < 0\) の両方が成り立っている必要がありますが、\(A \geq 1\) であるため少なくともどちらかは成り立ちません。

従って、頂点数が \(4\) の木に対してはスターグラフ以外にもスコアの総和の最小値を取る木があります。

次に一般の木について考えます。

次数が \(3\) 以上である頂点を頂点 \(1\) とし、頂点 \(1\) に隣接する頂点を \(3\) つ選んで頂点 \(2,3,4\) とします。（それぞれをつなぐ辺を辺 \(2,3,4\) と呼ぶことにします。）

辺 \(2,3,4\) を削除し、頂点 \(1, 2, 3, 4\) を新しくつなぎなおすとき、そのなかでスコアの総和が最小になるものを考えます。
スコアの総和への寄与を考えると、実は以下を考えればよいことが分かります。

• 頂点 \(1,2, 3,4\) を含むそれぞれの木について、書かれた値の総積を \(p_1, p_2, p_3, p_4\) とする。このとき、\(p_1, p_2, p_3, p_4\) が書かれた \(4\) 頂点の木であって、スコアの最小値はどれか。

これは頂点数が \(4\) の木に関する議論から、頂点 \(1,2,3,4\) がパスグラフとなるものに最小値が存在することが分かります。

以上から、次数が \(3\) 以上である頂点についてはそうでないように変換しても損しないものが存在することから、スコアの総和が最小値を取るグラフはパスグラフとしてよいことが分かります。

（※ 1） の証明

\(A\) を並び替えてもスコアの総和には影響しないので、都度適当に並び替えてもよいことにします。

以下の問題を考えればよいです。

数列 \(A\) が与えられる。\(\displaystyle \sum_{i=1}^N \left(\prod_{j=1}^i A_j + \frac{P}{\prod_{j=1}^i A_j} \right)\) が最小値を取るような \(A\) の並び替え方を求めよ。

\(\displaystyle A_{l,r} = \prod_{i=l}^{r} A_i\) とします。

\(i\) を、\(A_{1,i}^2 \leq A_{1,N} = P\) となるような最大の \(i\) とします。
\(1 \leq j < i\) である \(j\) について、\(A_j\) と \(A_{j+1}\) を入れ替えたとします。このとき、\(\displaystyle A_{1,j-1}A_{j+1} +\frac{P}{ A_{1, j-1}A_{j+1}} - \left(A_{1,j} + \frac{P}{A_{1, j}}\right)\) だけスコアが増加します。

ここで、

\[\displaystyle A_{1,j-1}A_{j+1} +\frac{P}{ A_{1, j-1}A_{j+1}} - \left(A_{1,j} + \frac{P}{A_{1, j}}\right) \\ = \left(\frac{P}{A_{1,j+1}}- A_{1, j-1} \right)\left({A_{j}} - {A_{j+1}}\right)\]

であり、\(A_{1,j+1}A_{1,j-1} \leq A_{1,i}^2 \leq A_{1,N} = P\) であるため 上記式の符号は \({A_{j}} - {A_{j+1}}\) の符号に一致します。
よって、\(A_j < A_{j+1}\) であるときより \(A_j > A_{j+1}\) であるときの方がスコアの総和が小さくなることが分かります。

以上より、\(A_1 \geq A_2 \geq \dots \geq A_i\) であるときにスコアの総和が最小となります。
\(A\) を反転させることで、\(A_{i+1} \leq A_{i+2} \leq \dots \leq A_{N}\) も示すことができ、（※ 1）を得ることができます。