【题解】 Wannafly挑战赛2

T1 Cut

采取逆向思维。问题就变成我们采取不断合并的策略，使得总代价最大。于是变成了经典的哈夫曼树题。每次从剩下的元素中挑选两个最大的进行合并，直至剩下一个元素。此题得解。

T2 Travel

通过一些观察可得：节点 到节点 的最短路肯定为以下两种情况之一：

1、不经过额外的 条边直接从 到 。

2、从先走到某个为额外边端点的 ，再从 走到某个同样为额外边端点的 ，最后从 走到 。

预处理所有额外边的端点间两两最短路，询问时暴力枚举更新答案即可。

时间复杂度： 。

算法二：

进一步观察可得，以上第二种路径可进一步化简为：从 先走到第一个为特殊边端点的 ，再从 走到最后一个为特殊边端点的 ，最后从 走到 ，这样的 和 都是与 和 相邻的。

故我们只需要预处理出与 相邻的两个和与 相邻的两个 ，就可以计算出答案了。时间复杂度： 。

T3 Butterfly

用 表示从 位置向下连续有多少个 ，用 表示从 位置向右下连续有多少个 ，用 表示从位置向左下连续有多少个 ，设 ，枚举蝴蝶的左上角 ，问题就变成了找到对应的右上角 ，使得 且 且 最大。移一下前面的式子，即我们要在区间 里找到最大的 ，使得满足 。我们把 按照 排序，随着 从左到右枚举，一点一点把 加进考虑的范畴，于是问题变成了在一段区间里找一个最大的 ，随便怎么弄都可以啦！std选择了线段树，也可以使用并查集路径压缩大法。复杂度

T4 Delete

考虑到图是 DAG 形态，那么删掉一个点 以后会发生什么呢？考虑拓扑序，一定有一条边从 的左边连接到 的右边。我们可以枚举所有的边 ，用 更新拓扑序中 区间的最小值。查询的时候线段树里找一找就可以啦！

T5 Mod

将 这个区间询问拆成两个前缀询问， 不动。问题形如 属于 ， 属于 ，将 模去 答案不变，因此可考虑对 和 进行辗转相除。令 ,原问题中的 属于。其中 属于。因为每个 至多对应一组 ,所以这就是求这个三元不定方程在限制下有多少组解。通过 的范围，算 的范围：