本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-15 15:22:31

听（我妈）说有人想跟我探讨这题做法，就写这题较为详细题解了。

先钦定 $1$ 是根节点。

可以先将每个点的答案分别计算出来最后取最小值。

为了方便计算，自然能想到分子树内和子树外分别计算，具体地，设 $f_i$ 表示 $i$ 为根的子树内离 $i$ 最远的关键点的距离，设 $g_i$ 表示 $i$ 为根的子树以外离 $i$ 最远的关键点的距离。

$f_i$ 的计算是很简单的树形 dp。

考虑 $g_i$，有两种转移。设 ${fa}_i$ 表示 $i$ 的父节点，${bro}_i$ 表示 $i$ 的兄弟节点。

• 从父节点继承，即 $g_i = g_{fa_i} + 1$。
• 从兄弟节点继承，即 $g_i = g_{bro_i} + 2$。

完结。

https://codeforces.com/contest/1881/submission/227980730