2022牛客OI赛前集训营-提高组（第三场）题解

A:一个显然的事实是，匹配只会考虑匹配排序后相邻的两个元素。
考虑先排序，令表示前个元素中，选取对的最小值。
则不选当前元素
选取当前元素:
两者取即可。总复杂度
B：显然删除完毕之后，将剩余的数字从小到大填入空位中。考虑从前往后扫描，对于每一位，考虑能否将这一位变得更小。若，则不该删除位置；若，则应该删除位置。
若，则假设删去第个位置之后，应该填入的数字是。若，则应该删去位置；若，则不应该删去位置；若，则删去位置本质上和删去位置是相同的，可以忽略位置。
若，则假设这一位本该填入的数字是，若存在满足且，则删去位置能使得位置的数字变小，故删去位置。（第一次碰到这种位置时,是唯一的）此时不考虑删去位置的情况，因为哪怕，其本质上也是等价的。
可以通过set维护"当前本该填入的数字"。

题解2:可以通过二分答案+哈希的做法比较删去位置和位置的优劣，故可以扫描一遍然后找到最小值。这个哈希值并不好维护，由于出题人没有实现过这个做法，细节方面留给读者思考。
C:先考虑所有边权都不为的情况应该怎么做。
首先不难看出，点集在树上的斯坦纳树即为其虚树。虚树上的边权和即为正确答案。
我们下面证明：该算法是正确的，当且仅当给定点集在上的虚树点集和相同。（另一个说法是，任意中的两个点的LCA也在中）
其充分性不难证明，下面证其必要性：
若存在属于虚树点集，且不属于的点（下面简称虚点），则在虚树上，虚点至少存在三条相关联的边。在斯坦纳树中，这三条边对答案的贡献是这三条边的权值和；而在我们建立的最小生成树中，至少有一条边的权值被计算了两次（由于虚点并不在原先的点集中，所以要让这三条边的另一个端点联通，就不得不经过其中一条边两次），因而答案就是错误的。
对于边权存在的情况，只需要将所有由边连结的连通块视为一个点，一个连通块被选中当且仅当其中至少有一个点被选中，然后应用上述做法即可。

关于如何维护虚点：可以考虑倒着做，每次删去一个点。如果删去的这个点有三条及以上的边相连，它就转型成为虚点。如果某次删除后，某个虚点只有两条边相连，则该虚点消失。答案为当且仅当不存在虚点时。


D:是一道巨大的DP题

的时候，可以打表。如果你打表了，可以注意到答案只有和，所以输出或者输出都能拿到分的好成绩！（忘记检查后面的数据点…导致输出有分，我谢罪TAT）
现在说说正解：
首先意识到，所有直径的中点都是同一个点（当长度为偶数时），或者中边是同一条边（长度为奇数时）。不妨令这个点为根（长度为奇数时，额外在边的中间添加一个点，令为根）。此时有根树无根树一一对应（因为对于每棵树，指定的点是唯一的）
下面以长度为偶数为例，如何计算直径条数？假设直径长度为，则叶子节点的深度至多为(令根节点深度为），我们将深度为的叶子称为有效叶子。不难看出，任意一对不属于根节点的同一棵子树的有效叶子会产生一条直径。

此时，可以令表示根节点的前若干个子树已经拥有了个节点，个有效叶子，和条直径时的答案。考虑一棵子树有效的信息只有两个，节点个数&有效叶子个数，令这两个的值为（下文中称为子树形态）。转移时按顺序枚举，并更新答案（注，上述写法有滚动数组的思想在，真正意义上，应该令，表示已经考虑前种子树形态（不同的)时的答案，然后让从处转移）。

为此，我们还需要用同样的技巧预处理一个数组，令表示一棵子树，拥有个节点，深度最深的点为，深度最深的点恰有个时的方案数。同样枚举每一种子树形态对答案的贡献并更新。
直径长度为奇数时，需要额外处理一件事：子树必须恰好为两棵（因为我们加入的额外节点只连结中心边的两个端点）。一个简单的做法是增加一维表示选取了几棵子树。
其实复杂度跑绰绰有余，不过为了放大常数过就还是设置了