今日解いた競プロの問題。

ABC267-F: 一応自力AC。なんかTwitterでそれっぽい図を見てしまった気もするが…

直径となる経路をまず求めておく。その経路上の頂点を根とした木を考えたとき、その木の中のある頂点Aから距離Kiの頂点を求めるには、その木上での祖先かもしくは最初に求めた直径となる経路をそれぞれ調べれば良い。その2か所に無ければ無い。

木上でのn個上の祖先を求めるアルゴリズムを思いつけたのが良かった。スタックに頂点を積みながら木の頂点をDFSで探索すると、各頂点を見ているときに根からの経路を持っていることが出来る。Level Ancestor Problemという有名問題らしい。有名なLCAもこれの応用だった。木上で高速に移動したいときは必須のテクとして覚えておこう。

---

部屋の整理をすこし進めた。無駄な発泡スチロールをいくつかより分け、書類束を頑丈な段ボールに移し替えた。