積が \(K \le 10^9\) 以下ということを言い換えると、掛かっている \(2\) 以上の整数は高々 \(30\) 個であると言い換えられます。
もし与えられるグラフが木である場合は次のようにして解くことができます。

• ボトムアップな木 DP をする。
• 各頂点では、 {始点からの積, 始点の深さ} の集合を管理する。
  • この時、始点からの積が増えるにつれて始点の深さも増えるように維持する。直感的な言い方では、無意味な要素は捨てておく。
• 各頂点にてマージテクを行いながら、パス全体の LCA がその頂点であるような解の最大値を求める。
• もしその頂点に書かれた整数が \(2\) 以上なら、その頂点が持つ集合全体の「始点からの積」の部分を更新する。
  • この更新は、ひとつの始点あたり高々 \(30\) 回しか発生しないことに留意。

時間計算量は \(O(N \log N (\log N+ \log K))\) といったものになりますが、実測は比較的高速です。

なもりグラフ上で 1 辺を使うように固定した場合は解説の方針と似たように処理できます。上記の木 DP のコードの一部を流用するような方針をとることもできます。

実装例 (C++)