ABC 401 F — Add One Edge 3

考察

二treeをedge(i,j)で結んだ後のdiameterは、元diameter d1,d2か、そのedgeを通るpathのどれかである。edgeを通る最長pathはiのeccentricity A_i+1+jのeccentricity B_jなのでf(i,j)=max(D,A_i+B_j+1), D=max(d1,d2)。treeの任意vertex vのeccentricityはdiameter両端u,wへのdistanceのmaxである。threshold jはA_iが増えるほど単調なのでtwo-pointerでも総線形、binary searchでも十分高速である。

採用する候補: 各treeのdiameter端点から全vertex eccentricityを求め、sort+prefix sumで全pair maxを集計する

Bを昇順にすると各A_iについてA_i+B_j+1≥Dとなる境界を二分探索でき、下側はD×個数、上側はB prefix/suffix sumでO(log N)集計できる。

棄却する候補: 各(i,j)で結合treeのdiameterをBFSし直す

N1N2 pairそれぞれ線形探索となり到底間に合わない。

各treeで二回BFS/DFSしてdiameter endpointsとdを得て、両端からdistanceを計算しeccentricity列A,Bを作る。Bをsortしprefix sumを作り、各aのlower_bound(D-a-1)でmaxの和を足す。

典型の発動条件

diameter endpointsによるeccentricity

発動条件: treeの全vertexから最遠点distanceを求めたいとき。

diameter二端へのdistanceのmaxを使う。

max(const,a+b)のsort集計

発動条件: 全pairにthreshold付き線形式を足したいとき。

一方をsortし境界とprefix sumで二群を計算する。

問題固有の要素

追加edgeを通るdiameter候補は両treeで接続点から最も遠い方向を独立に選べるため、各vertexのeccentricity一値だけで十分である。

別の問題へ持ち帰る視点: 二構造を一edgeで繋ぐ全pairqueryでは、cross pathのendpoint最適化を各側のsummaryへ分離する。

正当性

一辺i–jで結合した直径は元二直径の最大Dと、跨ぐ最長距離ecc1[i]+1+ecc2[j]のmax。tree最遠距離は直径二端から得る。Bをsortするとmaxの切替点が一つになり個数Dとsuffix和を厳密に集計できる。

実装上の注意

  • tree size1ではdiameter endpointとdistance0を扱う。総和はpair数×distanceで64 bit整数を使い、threshold等号をmax側に含める。

復習の核

  • 小tree全pairを実際に結んで全点対distanceを求め、single vertex、path、starの式を比較する。

計算量と制約

時間

木サイズN,M。二木eccentricity O(N+M)、B sort O(M log M)、各A二分探索 O(N log M)。

空間

二木、eccentricity、prefix和 O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \le N_1, N_2 \le 2 \times 10^{5}; 1 \le u_{1,i}, v_{1,i} \le N_1; 1 \le u_{2,i}, v_{2,i} \le N_2; Both given graphs are trees.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Add One Edge 3 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 基準点からの木距離・剰余類・直径・中心

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 木距離・直径・中心・最遠点

    補助タグ: 寄与の数え上げと順序交換

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 基準点からの木距離・剰余類・直径・中心

    • 一回または二回の木探索で少数の基準点からの距離を求め、一意経路・直径端点・中心の性質から頂点分類や最遠距離条件を整理できる。

    先に読む単元:

    • 局所寄与へ分解して集計順を交換する — 数える対象を一意に固定し、その対象を含む選択や組の個数へ集計順を交換する。要素・組・区間・値のどれを固定すると重複が消えるかを比較する。

    この解説で扱わないこと:

    • 根付き木の子状態を合成する木DP、およびLCA・HLDによるパスの区間分解。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題