动态直径相关
📝
内容提要
众所周知，求直径有两种经典方法，两次 dfs() 和树形 dp。其中前者要求边权非负。这是因为在边权非负的情况下，我们插入一个新节点，直径要么不变，要么其中一个点和原先的直径重合，因而经典的合并子树维护直径的算法也依赖这个性质。 盘点一下动态直径的做法基本也可以分为两大类： 链分治 这种做法是对 dp 做法的衍生，因为轻重边树链剖分（Heavy Light...
➡️
