ABC 401-500/ABC447F - Centipede Graph - 競技プログラミング用 知識集積所

---

問題

ABC447F

必要知識

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

• 隣接リスト※
• 木の直径※
  • 幅優先探索※

考え方

木であるためループは存在しない。
つまり、次数が4以上（両端だけ3以上）の頂点のみで構成されたパスの中で最長のものを探せばよい。
これは、以下の方法で処理できる。

まず、頂点数3Nの森を用意し、

• 次数2の頂点を少なくとも片端にもつ辺は削除する
• 次数3の頂点を使う場合、3回でi番、i+N番、i+2N番に1回ずつつなぐ
• 次数4以上の頂点を使う場合、全て同じi番につなぐ

という形でもとの木を作り直す。
そして、できた森の各木の直径※を調べ、その最大値を答えとする。

解答例

解答例

注意点

別解