ゲートを動かす場合は, 駒と同時に動かすとして良いです. また, 適宜操作 1 を行うことにし, 次の \(3\) つの操作を考えることにします.

• 操作A：駒とゲートが同じ頂点にあるとき, その頂点に隣接している頂点に駒とゲートを移動させる（隣接する辺を移動したとみなす）
• 操作B：駒がある頂点に隣接している頂点に駒を移動させる（隣接する辺を移動したとみなす）
• 操作C：駒をゲートがある頂点に移動させる（辺を移動せずに, ジャンプしたとみなす）

操作Aと操作Bにコストが \(1\) かかります.

操作Aを続けている間は駒とゲートは共に移動します. しかし, ひとたび操作Bを行うと, 操作Cを行うまではゲートはそのままの位置にとどまり, 操作Bによって駒が単独で移動を行う, ということになります. ここで, 操作Bでゲートのある位置に駒を移動させるのは無駄なので考えません.

初めに駒とゲートを置いた頂点を \(v\) とします. また, 最後に操作 C を行うことで, 駒とゲートは同じ頂点にいるときにのみ操作を終了できることにします.

ゲートが存在したことのある頂点とゲートが移動したことのある辺に A のラベルをつけ, それ以外の頂点および辺には B のラベルをつけます. Aのラベルをつけた頂点およびグラフからなる辺は連結であり, 特に部分木を成します. これを部分木 \(A\) と呼ぶことにします. \(v\) は部分木 \(A\) に含まれます.

また, Bのラベルをつけた辺であって, 端点の一方に A のラベルがついているものを, 境界辺とも呼ぶことにします.

B のラベルがついた頂点と, B のラベルがついた境界辺ではない辺は, いくつかの連結成分に分かれています. 特に各連結成分は木を成し, 境界辺によって部分木 \(A\) の頂点に接続しています. \(i\) 番目の連結成分は境界辺 \(e_i\) によって部分木 \(A\) の頂点 \(l_i\) に接続しているとし, \(i\) 番目の連結成分に \(e_i\) と \(l_i\) を追加したもの（これもまた部分木となる）を \(B_i\) とします.

次の \(3\) 点が重要です.

• 最適な操作では, A のラベルがついている辺を操作 B で通ることはないとして良い. なぜなら, 適切に操作の分解・並べ替え・置き換えを行うことで, 次のような流れで操作をしてもコストが増えないからである.
  • 駒とゲートは頂点 \(v\) から始め, 操作 A で部分木 \(A\) のすべての頂点に訪れ, 頂点 \(v\) に戻る. これを部分木 \(A\) の旅と呼ぶ.
  • その途中で \(l_i\) に訪れた場合は部分木 \(A\) の旅を中断する. 駒のみが頂点 \(l_i\) から始め, 操作 B で部分木 \(B_i\) のすべての頂点に訪れ, 頂点 \(l_i\) に戻る. これを部分木 \(B_i\) の旅という. その後, 部分木 \(A\) の旅を再開する.
    
  • 部分木 \(B_i\) の旅を行なっている間は, ゲートは常に頂点 \(l_i\) にあることに注意せよ.
• 最適な操作では, 境界辺 \(e_i\) を \(l_i\) から辿る向きに移動すること（必然的に操作 B で移動することになる）は \(1\) 回しかないとして良い. なぜなら, \(2\) 回以上移動するなら, \(1\) 回目の移動でゲートと共に操作 A で移動して, 最後に再びゲートと共に操作 A で \(l_i\) に戻っても, コストが増えないからである.
  • このことから, 部分木 \(B_i\) の旅では, 操作 C は最後に \(1\) 回のみ行うことになる.
• 部分木 \(A,B_i\) の旅では, その旅を始める頂点から最も遠い頂点を最後に訪れるべきである.
  • すなわち, 開始頂点から最も遠い頂点までの距離を \(d\) とし, 部分木内の辺の個数を \(e\) とすると, 部分木の旅にかかるコストは \(2e-d\) となる.

最後の考察で, 部分木に含まれる辺の個数の合計は必ず \(N-1\) なので, コストの最小化は \(d\) の総和の最大化に言い換えられます.

これらの考察をもとにすれば, \(v\) を固定したときの答えは木DPで計算できることになります. \(v\) を根に取ったときの木DPをし, \(u\) を根とする部分木の計算には次の情報を持てば良いです.

• \(u=l_i\) だとしたとき, 部分木 \(B_i\) の旅を終える頂点までの距離としてあり得る最大値
• \(u\) が部分木 \(A\) に入るとし, 部分木 \(A\) の旅を終える頂点が \(u\) を根とする部分木の中に現れるとしたときの \(d\) の総和の最大値
• \(u\) が部分木 \(A\) に入るとし, 部分木 \(A\) の旅を終える頂点が \(u\) を根とする部分木の中に現れないとしたときの \(d\) の総和の最大値

また, この計算は容易に全方位木DPに拡張できます. これによって, 旅を始める頂点をすべて調べることもできます. 時間計算量は \(\mathrm{O}(N)\) となります.