本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-06 22:10:42

Contest link

很遗憾没有 AK 比赛，原因在于 T4 我把 vector 当成了 set 用（排序是算法正确的基础之一），以及忘了处理取余结果为负数。

不过两位 hdu 队友以及 Cubber 都 AK 了，膜拜！！！！

T1

签到题。

注意到，推导最需要的信息包括 $a$ 的最大值和 $b$ 的总和，想要得到的信息是选择方案数。

首先，将所有 $(a_i,b_i)$ 按照 $a$ 升序排列。

令 $f_{i,j}$ 表示最大值不超过 $a_i$，且总和为 $j$ 的方案数。

$O(n^2)$ 暴力转移。

然后，最大值确定为 $i$，总和为 $j$ 的方案数则是 $f_{i,j}-f_{i-1,j}$。

然后暴力枚举最大值，总和，算出对应方案数总和。

时间复杂度 $O(n^2)$。

T2

和 T1 难度近似，但是存在一些误区会把一些比较幸运的人（比如我）引进去。

注意到，这实际上和括号匹配是类似的。

令 $f_{l,r}$ 表示 $[l,r]$ 区间内部完成匹配的操作方案数。

转移的话，则可以枚举 $r$ 匹配哪个位置，假设 $r$ 匹配位置 $x$，那么分别求解 $[l,x-1],[x+1,r-1]$ 的答案，然后将两个区间的答案合并。

两个区间的答案并不能简单的相乘，因为两个区间的操作顺序是互相独立的，每种不同的归并顺序都是一种新的方案。

两个区间实际上分别有 $\frac{x-l}{2},\frac{r-x}{2}$ 个元素，假设分别已经确定了顺序，每次可以在两个区间中任意选一个删掉，现在想要知道删完两个序列的方案数。

这个也是可以预处理的，$g_{i,j}$ 表示两个长度分别为 $i,j$ 的序列的归并方案数，$O(n^2)$ 暴力递推可以得到答案。

最终解法总复杂度为区间 DP $O(n^3)$ 加上预处理 $g$ 的 $O(n^2)$，即 $O(n^3)$。

T3

考虑一下什么时候最短路才会变化。

注意到，如果删除的边不在最短路上，那么一定不会改变最短路，可以直接跳过。

但是实际上可能有多条最短路，最短路上的边的数量同样可能到达 $O(n^2)$ 量级。

但是，注意到其实，只选择一条最短路，按住钦定其上的边为最短路上的边就可以了，因为只要有一条最短路仍然没断开，那么最短路长度仍然不会变化。

此时，只有 $O(n)$ 条边断开可能产生影响，每次 BFS $O(n^2)$ 计算新的最短路，可以通过。

T4

首先，观察一下最终走过的点的坐标形式都是什么。

令前 $n-1$ 次移动到达的点的位置集合（包括一开始的 $(0,0)$）为 $S$，第 $n$ 次移动后的点的位置为 $(dx,dy)$。

那么，对于所有 $Kn$ 次移动中到达过的点 $(x,y)$，必然满足以下两种情况至少一个：

• 存在一个非负整数 $k \lt K$，以及 $(sx,sy) \in S$，使得 $(sx+k\cdot dx,sy+k\cdot dy) = (x,y)$
• 存在一个非负整数 $k \le K$，使得 $(x,y) = (k\cdot dx,k\cdot dy)$

换个理解方式，就是对于任意 $(x,y) \in S,0 \le k \lt K$，$(x+k\cdot dx,y + k \cdot dy)$ 必然存在于最终经过的路径里，对于任意 $k \le K$，$(k\cdot dx,k \cdot dy)$ 也必然存在于最终经过的路径里。

首先，由于我不喜欢比较重要的地方出现负数，所以，如果 $dx,dy$ 某一个小于 $0$，那么就将整个的对应的横向或纵向翻转（比如说，U 换成 D，L 换成 R）。

答案一定不会改变，因为是对称的，然后，就能保证 $dx,dy \ge 0$。

然后，考虑按照顺序遍历 $S$ 中的每个元素，依次考虑遍历到的新元素，事实上对答案新增了多少个位置的贡献。

此时，就需要分析怎么计算当前的元素产生的位置里面，有哪些是和之前遍历过的元素产生的位置重复了。

回想一下判定条件。

假设当前扫描到了 $S$ 中的元素 $(x_1,y_1)$，然后需要知道其与 $S$ 中另一个元素 $(x_2,y_2)$ 有哪些位置重合。

• 首先，需要满足 $\frac{x_1-x_2}{dx} = \frac{y_1-y_2}{dy}$
  本条件的原因是，加上的 $dx,dy$ 分别乘上的倍数都是相等的。
  本条件可以转化为 $x_1\cdot dy - y_1 \cdot dx = x_2 \cdot dy - dx \cdot y_2$，这样等式两边分别都只包含来自同一个元素的值，以及差不多相当于常量的 $dx,dy$。
• 其次，需要满足 $x_1 \equiv x_2 \pmod {dx},y_1 \equiv y_2 \pmod {dy}$
  如果不满足这个，那么当然是不能相等的，因为不能有小数。
• 然后，需要满足 $|\frac{x_1-x_2}{d_x}| \lt k + [(x_2,y_2) = (0,0)]$。

综上，定义一个 $S$ 中的元素 $(x,y)$ 的类别属性为 $(x \cdot d_y - y \cdot d_x,x \bmod {d_x},y \bmod {d_y})$，只有两个 $S$ 中的元素的类别属性相同，它们才可能产生相同的位置。

考虑开一个 map，存储每一种类别属性的所有元素。

回到原来问题，此时可以发现，和 $(x_1,y_1)$ 处于同一种类别属性的元素中，有价值的仅包括 $x$ 方向，$y$ 方向上分别最接近的两个元素（总共 $4$ 个元素）。

当前元素产生的新位置的形式为 $(x_1 + k\cdot dx,y_1 + k\cdot dy)$，而原本情况下 $0 \le k \lt K + [(x_1,y_1)=(0,0)]$。

这些邻居元素，实际的影响就是使得一段前缀或者后缀的 $k$ 不合法，分类讨论一下就可以了。

map 里面开两个 set，分奇偶分别存储所有的位置就可以了。

对于 $(0,0)$ 这个特殊的点，它有一个 $k$ 可以等于 $K$ 的特权，为了简单处理这种情况，可以额外建立一个节点 $(dx,dy)$。

T5

先预处理 $f_u$ 表示 $u$ 到所有子树内节点的距离，以及 $siz_u$ 表示 $u$ 子树大小。

然后，再次 dfs 整颗树，并且搜索到每个节点时，都记录其子树外的节点到其距离总和，从父节点到子节点递归的时候，实时更新就可以。