CF1762

破防。掉分。

被 E 狠狠诈骗了。

A. Divide and Conquer

没啥好说的。和为偶数即为 ，否则算一下每个数改变奇偶性需要几次操作，取 。

B. Make Array Good

把 变成 的形式。

C. Binary Strings are Fun

每次只能添加两个数，因此若众数发生改变则有上一次两数出现次数之差等于 。这种情况下方案是唯一的。

而在连续相同段中可以任意填。随便算一下就好了。

数组开小吃了一发罚时。

D. GCD Queries

诈骗题。

最大为 。直接求最大 即可。

想了 没想出来。寄。

E. Tree Sum

小结论：

结论 ：设 表示与 相连的边权之积， 表示边权，则 。因此， 为奇数时一定无解。

结论 ：在有解时，一种树的形态唯一对应一种染色方案。从叶子节点向上染色可知正确性。

观察题目，发现不是计数而是算 到 路径长度和。

考虑拆边算贡献。

继续发掘性质。

结论 ：一条边权值为 当且仅当其连接的两个连通块大小均为奇数，否则这条边边权为 。同样自底向上染色，归纳可以证明。

加上题目已经提示了 个节点有标号无根树的个数是 ，可以直接枚举一侧连通块大小计算贡献。

设 表示 个点形成的有标号无根树数量，则

钦定 所在连通块大小为 ，

上式相当于：

• 先从剩下 个点中选出 个点形成 所在连通块。

• 两侧树的形态各有 与 种。

• 边的左右端点分别有 与 种。

直接算。

F. Good Pairs

绝对值很烦。

可以发现，**若方案中经过 三点且 ，则可以直接从 跳到 **。 为最小值同理。

于是，除去 的情况，中间经过的数一定严格单调递增或递减。

不妨考虑递减的情况。在原序列与翻转后的序列上各做一次，两次结果之和即为答案。

设 表示以 为终点的数对数， 为最大的满足 的下标。于是有

值域线段树上二分+值域树状数组维护即可。