考察
木の全頂点を訪れて出発点へ戻るwalkでは、各辺を切った両側を往復する必要があり、全辺を少なくとも二回使う。DFS巡回でこの下界は達成できる。終点を自由にすると、始点から終点までの一本のpathだけは戻らずに済む。節約できる重みを最大にするpathが木の直径である。任意の訪問walkに終点から始点へのpathを加えると閉路walkになり、その長さは少なくとも2ΣCなので元walkは2ΣC−dist(s,t)以上である。直径端からDFSし、直径へ進む枝を最後に回せば、直径辺を一回、他辺を二回通って下界を達成できる。
採用する候補: 全辺重みの2倍から重み付き木の直径を引く。
直径外の枝は往復し、直径上だけ一方向に進むwalkが下界2ΣC−Dを実現する。
棄却する候補: 開始・終了頂点の全組について、全頂点を訪れる最短walkを探索する。
端点選択と巡回順を同時に扱っているが、木では往復回数が辺ごとに決まり端点間pathだけが例外である。
辺重み総和Sを求める。任意頂点から最遠点uを探索し、uからの最遠距離Dをもう一度の木走査で求める。答えとして2S−Dを出力する。
典型の発動条件
木walkの辺横断下界
発動条件: 全頂点訪問で同じ辺を再利用でき、開始・終了位置が自由なとき。
辺cutの両側を訪れる必要性から往復回数を数える。
二回探索による重み付き直径
発動条件: 木上で最大端点間距離を求めるとき。
任意点の最遠点を一端とし、そこから最遠の距離を得る。
問題固有の要素
Hamilton pathという名前でも頂点の再訪が許されるため、問題は順列ではなくDFS巡回から一本の戻り道を省く形になる。
別の問題へ持ち帰る視点: 訪問問題では再訪可否を確認し、木なら各辺を何回横断すべきかへ分解する。
正当性
開始終了s,t間pathの辺は一回以上、それ以外は木のcutを出て戻るため二回以上通る。下界は2Σw−dist(s,t)、最小化には直径を引く。直径を背骨に枝を往復するwalkが下界を達成する。
実装上の注意
- 重み付きなので辺数ではなく距離和で最遠点を選ぶ。再帰深さを避ける実装と64 bitの合計値を用意する。
復習の核
- まず閉じたwalkの2ΣCをcut argumentで示し、開いたwalkとの差を端点pathとして説明する。直径探索が重み付きである点も明記する。
計算量と制約
時間
N頂点。辺和と二直径探索で O(N)。
空間
重み付き木と距離stack O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2\times 10^5; 1 \leq A_i, B_i \leq N; 1 \leq C_i \leq 10^9; All input values are integers.; Any pair of cities can be reached from each other by traveling through some roads.
出典