BZOJLuogu分析先建出圆方树。圆圆边的边权就为树上的边权，方圆边的边权为圆点到方点父节点的最短路。考虑树上最短路是怎么做的。求出 $\mathrm{lca}$ ，然后答案是 $dis[u]+dis[v]-dis[lca]*2$ ，这里的 $dis$ 是到根的距离。那么圆方树上是一样的，只是要分类讨论一下。如果 $\mathrm{lca}$ 是圆点，那么和树上是一样的。如果 $\math...
LuoguBZOJ分析和仙人掌最大独立集类似，不过难一些。设 $f[i]$ 表示 $i$ 子树中以 $i$ 为端点的最长链的长度。如果当前边是桥，直接转移，同时更新 $ans$ 。否则当前边在环上，先不处理。假设我们现在在 $u$ ， $v$ 已经被访问过了。那么 $u$ 是这个环的底端， $v$ 是这个环的顶端。我们把这个环找出来单独考虑。先考虑怎么用环上的点更新答案。要求的实际上是 $\...
BZOJ分析我们在 $\mathrm{tarjan}$ 的同时跑 $\mathrm{dp}$ 。设 $f[i][0/1]$ 表示 $i$ 子树中， $i$ 选/不选的最大独立集大小。如果一条边是桥，那么和树上独立集一样的转移。否则，这条边在环上，那么暂时先不转移。假设我们现在正在 $u$ 点，$v$ 点已经访问过了，那么 $v$ 是这个环的顶端， $u$ 是这个环的底端。这时我们可以通过跳父...