A 哈密顿回路

被阴间到了，给了一个 $G_{i,j} < G_{i,k} + G_{k,j}$ 的没用条件看了很久发现确实没用，最后暴搜一下就跑过去了。。

我们折半搜索一下，具体来说，对于 $n = 14$ ，我们搜出 $1$ 出发的所有点的个数为 $7$ 的路径，再搜出所有 $1$ 出发点的个数为 $8$ 的路径，然后拼起来即可。复杂度大概是一个和 $\binom{13}{6}$ 有关的东西。

写完后试了试，发现跑的非常慢。这里写一下我的优化方法：

• 由于最后只需要合并一次，不需要开 set / map 之类的东西，可以直接拿 vector 存下来，合并的时候排序双指针
• 由于跑 $7,8$ 的路径看起来还是需要 900ms 左右，我们考虑只跑 6,7 的路径，合并的时候多枚举一对点来合并，因为这题时间瓶颈进本在搜索，这样操作一下就只需要 300ms 左右了！

B 旅行

好题！

可以发现这个题就是让你按照某个 dfs 序来遍历所有叶子，求便历完后最大路径的最小值。

暴力 $dp$ 非常简单，直接设 $dp[u][x][y]$ 表示 $u$ 子树是否存在 $x$ 出发 $y$ 结束的路径。合并就直接合并，经过一番分析可以发现这个东西复杂度是 $O(n^4)$ 的。

看到求最大路径的最小值会想到去二分答案一下。于是现在问题就变成了一个点只能跳到距离它小于等于 $mid$ 的点，求是否可以跳完所有点。

我们考虑一个 dp 。可以设 $dp[u][x]$ 表示只考虑 $u$ 的子树之内，如果从 $x$ 出发，是否存在一条走完所有点的路径。这里有一个非常重要的贪心，由于你已经二分了答案，这个时候你就只需要存下从这个点出发能到达的深度最低的终止点了。而一条路径是双向的，所以这个东西其实也是结束在 $x$ 的最优路径。

那么合并就会非常简单，就是考虑两个儿子，然后枚举一对点，看看第一个儿子从 $x$ 出发，第二个儿子到 $y$ 结尾，中间两边结束的两个点的路径是否小于等于 $mid$ 。

但是这样做复杂度仍然是 $O(n^2)$ 的，考虑优化。这种二叉树，合并的题，看起来就很像可以启发式合并的东西。于是考虑怎么把一个点的状态压下去。首先，较小的子树显然只会贡献 $O(\text{minsize})$ 的合法初始点。而考虑如果从较大的子树开始，那结尾点的个数也只会有 $O(\text{minsize})$ 个。而结尾点相同的时候，显然初始点是越浅越好的。所以我们求完一个点的 $dp$ 状态后可以把所有状态按照终止点的位置去重，这样一个点的总状态数就是 $O(\text{minsize})$ 了。

按照启发式合并的经典分析办法，显然这个东西复杂度是 $O(n\log n)$ 的。因为一个点只会作为 $O(\log n)$ 次轻儿子。

C 守卫

神题！感觉这个转化非常妙，而且代码长但难度不高

首先考虑一个点的询问怎么办。就是求距离一个点距离小于等于 $r$ 的点的个数。这是一个经典的点分树问题。我们建立出点分树，然后就是从一个点开始往上跳，跳的过程中顺便容斥即可。这里和 震波 一题一样，就不赘述了。

我们考虑在询问两个点的时候怎么办。有一个非常显然的容斥，直接把两个点的邻域分别求出来，然后减去共有部分即可。而一个显然的结论是共有部分其实也是一个邻域，但是由于这个邻域的中心可能在一个边的中间，我们可以考虑在边中间在建立一个点。

那么在询问多个点怎么办？这里有一个非常神仙的操作。我们把每个点的 $r_i$ 设置成所有能覆盖到这个点的询问所导致它获得的 $r_i$ 的与这个点本身的 $r$ 取最大值。具体来说，对于一个邻域 $(u_k,r_k)$ ，我们让 $r_i = \max\{r_i , r_k - dis(i,k)\}$ 。这个部分可以两次 dfs 解决，具体来说，我们从下往上求出每个点只考虑子树内的情况，再从上往下一次即可。

在这样操作之后，会发现一个非常有用的性质：能够覆盖到一个点的所有邻域会形成一个联通块！由于这题在树上，树上的联通块有关的统计有一个非常经典的操作，我们考虑点减边容斥一下，于是每个点就正好会被统计到一次了。具体做法就是求出每个点覆盖到点的个数和，再减去所有边的。

但是 $Q$ 次询问怎么办？不难发现直接建立虚树用一样的做法即可。

复杂度 $O(n\log n + q\log n)$ 。注意点分的时候需要预处理一下一个点到每个点分中心的距离，不然写成两个 log 非常容易 TLE 。