与えられるグラフは「なもりグラフ」と呼ばれるグラフであり、木に辺を一つ加えて得られるグラフです。 このグラフにはサイクルがちょうど一つあり、それを \(C\) とします。

部分点解法

任意の \(2\) 頂点 \(u, v\) について、与えられるグラフ上に \(u\) から \(v\) への単純パスは高々 \(2\) つしかありません。 （サイクル \(C\) 上を通るとき、その方法が \(2\) 通りあります。） したがって、ある頂点をパスの端点に固定すると、その頂点が端点となる単純パスは \(O(N)\) 個です。 これらの単純パスは、その頂点から DFS することで、総積を管理しながら \(O(N)\) 時間で探索できます。 すべての頂点を端点として試すことで、 \(O(N^2)\) 時間で解けます。

部分点解法のコード例

満点解法

サイクル \(C\) 上の辺 \(e = \{u, v\}\) を一つ任意に選びます。 以下では、辺 \(e\) を用いて場合分けを行いその最大値を出力することで、 \(O(N \log N)\) 時間で本問題が解けることを示します。

(1) 辺 \(e\) を通らないときの最大長

まず、条件を満たすパスのうち辺 \(e\) を通らないものの最大長を求めます。 そのためには辺 \(e\) を削除して得られる木に対して本問題を解けばよく、これは重心分解を用いて解くことができます。 具体的には、以下のアルゴリズムです。

1. 木の重心 \(c\) を求める。
2. 条件を満たすパスのうち \(c\) を通るものの最大長を求める。
3. \(c\) を削除して得られる各連結成分（木）に対して、再帰的に計算する。

2 については、 \(c\) を端点とする各辺について、「\(c\) からその辺の方向に長さ \(\ell\) パスを伸ばすときの総積の最小値」の \(\ell\) に関する配列を計算し適切にマージすることで計算できます。 これは現在考えている木の頂点数を \(t\) として \(O(t)\) 時間または \(O(t \log t)\) 時間で計算できます。 それぞれ、全体の計算量は \(O(N \log N)\) 時間と \(O(N \log^2 N)\) 時間になります。

重心分解や計算量解析、その実装については Frequency Table of Tree Distance を参考にしてください。

(2) 辺 \(e\) を通るときの最大長

次に、辺 \(e = \{u, v\}\) を通るパスの最大長を求めます。

このとき、計算するべきものは、上図のように

• 頂点重みの総積を \(K\) 以下に保ちながら
• \(u, v\) からそれぞれ、頂点を共有しないように二本のパスを伸ばす

ときの最大の長さ（の和）です。

頂点 \(u, v\) から伸ばすパスのもう一つの端点をそれぞれ \(u', v'\) とします。 頂点 \(u'\) を固定したとき、図のように頂点 \(v'\) として選べる頂点の集合 \(R\) が定まります。

「 \(R\) の範囲内で \(v\) から長さ \(\ell\) パスを伸ばすときの総積の最小値」の \(\ell\) に関する配列があらかじめ計算されていれば、 \(u'\) を固定したときの最大長は二分探索で \(O(\log N)\) 時間で計算できます。 ここで、 \(u'\) に対する頂点集合 \(R\) は、 \(u'\) に最も近い \(C\) の頂点 \(\mathrm{root}(u')\) のみに依存します。 また、 \(u\) から \(\mathrm{root}(u')\) への（ \(v\) を経由しない）距離に対して単調性があります。 したがって、 \(u\) と \(\mathrm{root}(u')\) の距離が遠い順に \(u'\) をすべて試すことで、動的かつ効率的に上述の配列を管理でき、全体で \(O(N \log N)\) 時間で辺 \(e\) を通る条件を満たすパスの最大長が計算できます。

クレジット

原案： nu50218

解法： nu50218, Levixi, Jinapetto, akua

問題準備・解説： nu50218

レビュー： Jinapetto

テスター： physics0523