考察
二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.
出典