ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC019 D - 高橋くんと木の直径

問題
提出コード
電車の中で思いついたので慌てて書きました。

解法

いたってシンプルです。
まず、頂点1を根とする木について考えます。
頂点1とその他全ての頂点との距離を求め、距離が最大になったものを記録しておきます。
すると、その最大になった頂点を根と考え直したとき、その根からの距離が最大になる部分が、木の直径となります。
制約が大きなヒントになっているはずなので、部分点はそのまま全探索すればいいんだろうな、というところから、そして満点解法は、ある頂点に対して全ての頂点との距離を調べるor順番(1と2、3と4...)に一通り調べる、という操作が合計2回しかできない、ということから、どのように調べれば答えがわかりそうか、という方向で考えていきました。