ABC 401-500/ABC401F - Add One Edge 3 - 競技プログラミング用 知識集積所【6/13更新】

---

問題

ABC401F

必要知識

B以下レベルの内容は省略

• 木の直径（未作成）
• 隣接リスト（未作成）
• 幅優先探索（未作成）
• 累積和

考え方

木の直径（未作成）の求め方は、普通のアルゴリズムでやればよいとして、問題は計算量。
愚直にやると、N1*N2パターンのグラフ全部について直径を求めることになり、計算量がとんでもないことになる。
そこで、どうやって効率化するかを考える。

全てのグラフを、「直径が片方のグラフ内で収まるもの」「直径が片方のグラフ内で収まらないもの」にわけて考える。

前者は、全体の直径として2つの木の直径の大きい方を採用すればよく、それに個数を掛けておけばよい。

後者は、木1側の接続点から最遠点までの距離+木2側の接続点から最遠点までの距離+1が直径となる。

つまり、イメージとして入力例1の場合はこんな感じ。

木2＼木1		最遠点まで0	最遠点まで1	最遠点まで2
		0個	1個	2個
最遠点まで0	0個	直径2が0本	直径2が0本	直径3が0本
最遠点まで1	1個	直径2が0本	直径3が1本	直径4が2本
最遠点まで2	2個	直径3が0本	直径4が2本	直径5が4本

左上の直径が2になるエリアが合計0個で、2*0=0。
残り6マスが0+3+8+0+8+20=39。
合計で39。

最遠点を求めるのが大変そうに思えるが、実は最遠点は木の直径（未作成）の両端どちらかなので、両方から全頂点までの距離を幅優先探索（未作成）をすればすぐ。

ただし、これでもまだグラフが直線的になると表のサイズがN1*N2になってTLE。
そこで、木ごとにわけて以下のように計算する。
つまり、「そこが接続点になるものがいくつあるか考え、最遠点までの距離を掛ける」というのを木1木2それぞれの全頂点に対して行えばよい。
これは頂点1つずつ行わなくても、最遠点までの距離が同じである点はまとめて計算することができる。

• 木1の「最遠点まで0」の点（0個）について
  • 木2の「最遠点まで1以下」の点が1個なので、2*(0*1)=0
  • 木2の「最遠点まで2以上」の点が2個なので、とりあえず木1側と追加した辺の分だけ計算して1*(0*2)=0
• 木1の「最遠点まで1」の点（1個）について
  • 木2の「最遠点まで0以下」の点が0個なので、2*(1*0)=0
  • 木2の「最遠点まで1以上」の点が3個なので、とりあえず木1側と追加した辺の分だけ計算して2*(1*3)=6
• 木1の「最遠点まで2」の点（2個）について
  • 木2の「最遠点まで-1以下」の点が0個なので、2*(2*0)=0
  • 木2の「最遠点まで0以上」の点が3個なので、とりあえず木1側と追加した辺の分だけ計算して3*(2*3)=18
• 木2の「最遠点まで0」の点（0個）について
  • 木1の「最遠点まで2以上」の点が2個なので、木2側だけ計算して0*(0*2)=0
• 木2の「最遠点まで1」の点（1個）について
  • 木1の「最遠点まで1以上」の点が3個なので、木2側だけ計算して1*(1*3)=3
• 木2の「最遠点まで2」の点（2個）について
  • 木1の「最遠点まで0以上」の点が3個なので、木2側だけ計算して2*(2*3)=12
• 以上を合計して39。

最遠点が指定の数以上/以下の個数は累積和を使えばよい。

解答例

解答例

注意点

別解

畳み込み（未作成）を用いる

表が大きすぎる問題から先、表の斜め成分はまとめて扱えることを利用して、高速フーリエ変換による畳み込みを用いることもできる。
解答例