算法一

封锁 $(a,b)$ 是合法的，这等价于加入赛道 $(a,b)$ 后可选的最大路径数会从 $k$ 增加到 $k+1$。考虑枚举所有路径，对于每个情况按照定义求出最大路径数。

显然最大路径数可以通过树形 dp 进行计算。设 $f_u$ 表示考虑所有两端点均在 $u$ 的子树的路径，此时的最大答案。此时分成两类转移情况讨论，要么选择的路径均不经过 $u$，那么这一情况的最优解即 $u$ 的所有直系孩子的 $f$ 之和。否则枚举选取哪个路径，这一情况的贡献是 $1$ 加上与这条路径相邻的所有节点的 $f$ 之和。

时间复杂度 $O(mn^3)$，期望得分 $32$ 分。

算法二

考虑优化 dp 的效率，我们记 $g_u$ 为其所有直系孩子的 $f$ 之和减去 $f_u$ ，则不难发现 $g_u$ 对于路径情况的转移就是所选路径上 $g$ 的和再加 $1$。通过一个树状数组即可维护。

时间复杂度 $O((n + m \log n) \times n^2)$，期望得分 $40 \sim 44$ 分。

算法三

我们对于计算最大路径数有两种不同角度的观察：

1. 显然 $g$ 的值要么为 $0$ 要么为 $-1$，这表示事实上 $g$ 就是代表达到子树中最优解是否必须有一条路径穿过 $u$，这当且仅当存在一条路径经过的 $g$ 均为 $0$。
2. 这也可以看成一个贪心，我们仅仅是按照路径的 lca 自底向上贪心，能放就放。

考虑通过这种贪心思路来计算解，我们只需在 dfs 的过程中额外维护一个 vis 数组，表示 “这个节点是否上面有一个父亲已经作为某条被选择路径的 lca”。未被染色的节点显然时刻都是与根节点相连的一个连通块。我们每次选择一条路径，只需把该节点子树中与之相邻的未被染色的节点染色。检查一条路径的时候，只需检查两端点是否均未被染色。这样就可以做到线性。

时间复杂度 $Θ((n+m) \times n^2)$，期望得分 $44$ 分。

算法四

我们提出如下观察：假设一个节点 $u$ 满足加入路径 $(u,u)$ 能够使得最大路径数增加，则称节点 $u$ 是 ok 的。那么一条路径加入后能使最大路径数增加，当且仅当路径上的节点都是 ok 的。

之前的过程中我们对于根的选择是任意性的，接下来我们考虑以一个节点为根的时候，穿过它的路径如果能够增大最大路径数，此时显然等价于路径上的节点均未被选中，也就是在贪心过程中这条路径就可以被选。

我们考虑染色之后与根节点联通的未被染色的连通块，这应当与与 $u$ 相邻的 ok 的节点所构成的的连通块是一致的。因为我们考虑在未被染色的这个连通块内进行换根，其他子树必然没有发生结构变化所以染色情况不变，因此穿过这个连通块的所有路径均不能选，在这个情况下染色数组完全没有变化，因此这个连通块的任何一个节点都是 ok 的。

我们只需以每个点为根进行一次算法三的操作，然后对于每个连通块，对答案的贡献就是连通块大小的平方。

时间复杂度 $Θ((n+m) \times n)$，期望得分 $60$ 分。

算法五

考虑如何快速计算一个节点是否 ok。注意到贪心选择出的每条路径的 LCA，在任何一组最大路径集合中，这些节点都必然各自被一条路径覆盖。因此我们考虑将贪心选择出的每个路径及其 LCA 作为基础，发现在 LCA 的子树中的，不经过其他 LCA 的这一连通块内部，不 ok 的节点显然是该 LCA 对应的路径的一个子段。为了注意到为了让一颗子树里的节点不被覆盖，我们可以通过更换路径使得新的不与其他路径冲突的路径，用于更新原本路径 ok 的部分。注意在此时可以牺牲上方的空间，因此这个思路必须是自顶向下更新的。

因此两类路径可以用于更换被选路径：

1. 该路径的 LCA 是 ok 的，此时显然这一路径已经与某条路径相交，如果只与一条路径相交，则可以更新该路径。
2. 该路径的 LCA 和某个 LCA 重合，且不与其它路径相交，此时可以更新该路径。

对于如何快速判断一条路径是否只与一条路径相交，与哪条路径相交，我们可以打一个标记分为 $0,v,−1$，表示这一节点向上被选择的 LCA 有 $0$ 个，有 $1$ 个并标记其编号，或者有 $≥2$ 个。这样只需通过 dfs 即可更新标记，且一个节点只会被更新 $2$ 次。

通过离线处理，我们可以做到时间复杂度 $O(n+mα(m,n))$，如果使用 $O(n)−O(1)$ LCA 技术也可以做到 $O(n+m)$ ，期望得分 $100$ 分。