题解：P14390 [JOISC 2017] 自然公园 / Natural Park

· · 题解

这题部分分比较有启发性，但是我怎么会树不会图。

考虑怎么做链。关键在于你知道 0 是链头，于是你每次抓一个编号最小的节点，二分其路径上编号最大的节点。先 check 这个点能不能直接到达链头，若能则直接连上；否则可以找到链头到你找的节点路径（不包括两端）的最大值，递归处理最大值左边的部分，再处理右边的部分即可。大致过程如下图：

其中绿色节点为每次找到的路径上的编号最大值，或直接加入链头的那个点。

尝试扩展到树上。发现我们在链上扩展链头的过程可以看成在维护一个连通块，因此我们考虑在树上维护一个包含 0 的已知的连通块，每次加入一个节点。同样的，我们每次找到一个编号最小的未在连通块内的节点，尝试加入其到连通块的链。

但是你发现这样判点是否与连通块相邻会出问题：我们并不知道这个点到底与哪个点相邻！能不能考虑二分这个点呢？按普通编号二分是不可以的，这样子二分得到的会是 0 到该点路径上的编号最大值，因此我们需要一种编号使得每条从 0 开始的路径的末端都是该路径上编号最大的点。不难想到按照 dfs 序重编号即可。过程与上述类似，就不放图了。

现在考虑扩展到图上。问题到了图上，树上的做法会出现什么问题呢？

不难发现，若是按照树的做法去做，我们只能够得到原图的一棵生成树，并不能得到原图，原因就是我们在加入一个点时并没有加入所有这个点连到已确定连通块的所有边。于是接下来我们尝试去找到这些边。

我们第一次找到的是连向连通块内 dfs 序最小的点，我们不希望这个点再对我们找剩余的边产生影响。怎么办呢？我们把它直接删掉！然后，连通块剩下的部分可能会分成若干连通块，我们在这些连通块内递归寻找即可。询问次数会不会爆炸？由于题目保证每个点度数至多为 7，因此我们删掉一个点至多分出 7 个连通块，所以我们每次至多会在 7 个连通块内浪费询问，可以接受。

找出连通块内边的过程大致如下图：

其中，绿色点为我们想要加入连通块的点，加粗的边为我们每次找到的边。

这样，我们就以 O(n \log n) + 7m 的询问次数解决了问题。