本解説では木 \(1\) を \(G_1\) 、木 \(2\) を \(G_2\) と呼びます。

初めに \(G_1\) と \(G_2\) の直径を求め、\(d_1,d_2\) とします。

グラフに頂点 \(i,j\) を結ぶ辺を一本追加したとき、直径は \(\max(d_1,d_2)\) のままか、追加した辺を含むものに変化するかのどちらかです。

また、追加した辺を含む最長パスは、\(G_1\) 内で頂点 \(i\) から頂点 \(i\) の最遠点までのパス + 追加した辺 + \(G_2\) 内で頂点 \(j\) から頂点 \(j\) の最遠点までのパス となります。

このことから、各頂点についてグラフでの最遠点までの距離を求め、\(G_1\) での頂点 \(i\) についての値を \(A_{i}\)、\(G_2\) での頂点 \(j\) についての値を \(B_j\) とすると、\(i,j\) を決めたときの直径は \(\max(\max(d_1,d_2), A_i+B_j+1)\) と表されます。

補足： \(A,B\) を求める手続きについて簡単に述べます。直径を求めるアルゴリズムでは、直径の端点 \(2\) つを求めることができます。このとき、直径の端点を \(u,v\) とすると、\(A_i\) は \(\max(\mathrm{dist}(u,i),\mathrm{dist}(v,i))\) により求めることができます。（略証：\(A_i\) が \(\mathrm{dist}(u,i),\mathrm{dist}(v,i)\) より大きいと仮定すると直径の定義と矛盾）

以下、上式の総和を求める方法を考えます。

\(A,B\) を昇順に並び替えると、 \(A_i+B_j+1 \geq \max(d_1,d_2)\) を満たす \(j\) の値は \(i\) が増加するにつれ単調に減少するので、尺取り法が適用できます。もしくは、毎回二分探索をしても問題ありません。どちらにせよ、高速に上式の値を求めることが出来ます。