類似度 \(1\) が達成可能です。

以下では、頂点 \(v\) を見ているときの \(P_v\) の値のことを「 \(P\) の値」と呼ぶ感じの言い回しをします。

重心が \(1\) つの辺上にある場合

すなわち、ある辺が存在してその辺でちょうど \(N/2\) 頂点ずつに分割される場合です。

重心がある辺の位置から始めて、 \(2\) つの部分木でそれぞれ BFS の順番を取得します。その後、片方の BFS の順番ともう一方の BFS の順番を入れ替えるように \(P\) の値を振ります。

例えば、 \(2\) 回の BFS で訪れた順番がそれぞれ \((2,4,6,8,10)\) と \((1,3,5,7,9)\) なら、

• \(P_2=1\) , \(P_1=2\)
• \(P_4=3\) , \(P_3=4\)
• \(P_6=5\) , \(P_5=6\)
• \(P_8=7\) , \(P_7=8\)
• \(P_{10}=9\) , \(P_9=10\)

とします。

類似度が \(1\) であることを確認します。

• パスが重心を含む辺を通らない場合、頂点の番号と \(P\) の値が \(1\) つも一致しません。

• パスが重心を含む辺を通る場合、得られるパスは例えば

  1. 部分木 \(A\) の BFS の逆順、 \(P\) の値は部分木 \(B\) の BFS の逆順
  2. 部分木 \(B\) の BFS の順、 \(P\) の値は部分木 \(A\) の BFS の順

  の \(2\) 段階で構成されていて、類似度は \(2\) 以上になりません。

重心が \(1\) つの頂点である場合

重心は頂点番号と \(P\) の値を一致させます。

さっきのように BFS 順をぴったり入れ替えられるとは限らないので、代わりに、重心の隣接頂点から遠ざかるように BFS した探索順をすべてつなげて \(\lfloor (N-1)/2\rfloor\) 要素だけ配列を回転させます。部分木の頂点数は \(\lfloor (N-1)/2\rfloor\) 以下なので、頂点と同じ部分木の頂点番号が \(P\) の値に割り当てられることはありません。

重心が \(1\) 、 BFS 順がそれぞれ \((2,3,4),(5,6),(7)\) だとすると、 \(P=(1,5,6,7,2,3,4)\) となります。

類似度が \(1\) であることを確認します。

• パスが重心を通らない場合、頂点の番号と \(P\) の値が \(1\) つも一致しません。

• パスが重心を含む辺を通る場合、得られるパスは例えば

  1. 部分木 \(A\) の BFS の逆順、 \(P\) の値は部分木 \(A\) 以外の BFS の逆順
  2. 重心
  3. 部分木 \(B\) の BFS の順、 \(P\) の値は部分木 \(B\) 以外の BFS の順

  の \(3\) 段階で構成されていて、類似度は \(2\) 以上になりません。