May 4, 2024
众所周知，求直径有两种经典方法，两次 dfs() 和树形 dp。其中前者要求边权非负。这是因为在边权非负的情况下，我们插入一个新节点，直径要么不变，要么其中一个点和原先的直径重合，因而经典的合并子树维护直径的算法也依赖这个性质。
盘点一下动态直径的做法基本也可以分为两大类：
这种做法是对 dp 做法的衍生，因为轻重边树链剖分（Heavy Light Decomposition）也可以看成是链分治（Centroid Path Decomposition），所以我们把各种树链剖分也算在内。
动态树和 Top Tree 也都可以从链分治的视角来审视，
所以至少有下面三类做法：
还有一类做法是基于边权非负时直径的可合并性，这衍生出另外几种做法，
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。