还记得那年掀起了巨大风波的 ICPC 上海赛点吗？

那年的上海赛点掀起了巨大风波，起因其实就是一道网络流的题目。

那道网络流的题目在最短路径理论时间复杂度不可过的情况下，用 SPFA 作为 std 卡掉了不少高水平队伍的 dijstra 算法。

该题出题人和选手、裁判等在公众平台起了不小的冲突，实诚“我心里的那朵花”。

今天我们就是要来看看事件背后的这场比赛，2019年上海ICPC区域赛的题目。

题目链接

https://ac.nowcoder.com/acm/contest/4370

我们队伍现场比赛的花絮

• 这场比赛因为在上海，所以我们队伍当时是打星参赛的。
• 我愿称这场比赛为 ICPC·Tree Round，这可能和比赛命题是层层外包密不可分，直接导致了题目类型不平衡。
• 于是，很不巧的，这场的题目，按照垃圾分类的传统（我们队伍各自做各自擅长题目的战术名称）全是我的题。
• 被 F 关了两个小时，没有模板纯自己发明，好在发明成功了。
• 一进场就发现 K 气球颜色不是 black 了，就知道这个 K 一定有问题，于是开场就看了 K ，可以上来忘记考虑数据组数 TLE 了一发。

Problem B

题意：判断给出的所有字符串是否存在其中一个是另一个的前缀。

题解：直接把每一个字符串插入字典树，插入一个单词的时候，以下两种情况就是产生前缀关系了：

• 单词的结尾是已经存在的（为已经插入字符串的前缀）；
• 插入的过程中遇到了单词结尾的标记（已经插入的字符串存在当前串的前缀）。

Problem D

题意：给出一张 n 个点的完全图，要求移除尽可能多的 n 个点的生成树。

题解：n=2k 时，可以从 n-2 的情况推到 n ：n-2 的情况下有 \frac{n-2}{2} 棵生成树，对第 i 棵生成树连接 2i-1 到 n-1 ，2i 到 n 的边，再新建一颗生成树，有所有 2k 到 n-1 ，2k-1 到 n 的边，再加上一条 n-1 到 n 的边。

对于 n=2k+1 的情况，从 n-1 的第 i 棵成树连接一条 i 到 n 的边。

Problem E

题意：给出一个矩阵，起点和终点，每次进入一个没经过的方块时会获得这一步跨过的两个方块权值乘积的收益，在终点时可以选择不退出，起点默认被经过，求最大收益。

题解：本质就是网格图的最大生成树。全是 Weaver_zhu 想的，Kilo_5723 帮忙重构了代码。

Problem F

题意：要求支持树上三个操作：链加，链乘，链覆盖，维护链的立方和。

题解：树上的问题，通过树链剖分就转换成区间问题了。

于是就变成了维护区间立方和，要求支持区间加、乘、覆盖。

区间加、乘、覆盖需要三个延迟标记维护。

立方和的维护，通过立方和的展开来做，同时维护平方和以及和即可。

没什么意思的胖题，挺难写的，线段树部分调了挺久。

Problem H

题意：要求将树切割成 k 部分，使得每一部分点权和的最大值最小。

题解：显然二分答案，考虑如何验证答案。f[i] 表示当前结点 i 所在的联通块的点权和。

显然对于每一个节点，将其所有孩子的 f[x] 排序以后，从小到大依次往父亲里塞。

塞不下的，就只能切断了，也就是形成单独的联通块，塞进父亲里的，更新到父亲的 f[fa] 中，可以继续和上面的节点合并。

如此可以判断出在有限的点权和情况下，做多可以切割的块数。

Problem K

题意：保留最多的边，使得图中没有奇环。

题解：看到奇环，马上就能联想到二分图。

因为只有 16 个点，于是可以枚举每一个点属于哪一边，然后只保留两边之间的边，枚举所有的情况，求保留做多的边数即可。