这大概是我打得最丢人的一场 div1（虽然是 vp），比那场 FST round 还丢人（
实际上是因为 A2&B 太毒瘤，就直接没看 CDE，实际上 CDE 都是弱智题……
- A1
如果存在度数为 (2) 的点，只要让这个点的两条边上的数字不同即可。其他情况均可构造，具体方案可以从下一题中拓展出来。
- A2
由于保证边权两两不同，无解情况和上一题相同。
首先考虑一个简化版的问题：每个点的度数 (in {1, 3})。这种情况下，考虑 dfs 的过程。
若当前位于某个叶子 (d)，则直接返回一个 "接口"，形如 ((d, v))，其中 (v) 表示连接 (d) 与其父亲之间的边权。
否则，设当前位于 (i) 的子树，已经遍历完了 (i) 的两个儿子，并获得了这两个儿子的 "接口" 列表。假设两个儿子的接口中，(v) 之和恰好为连接儿子的边权值，我们试图归纳地将 (i) 的 “接口” 中 (v) 之和也变为连接 (i) 父亲的边权值。实际上，这就是一个三元一次方程组，解一下就可以知道将两个儿子中 (v) 之和为多少的 “接口” 对接成一次操作。剩下的 “接口” 可以直接放到 (i) 处。注意在一次对接中，不一定要将两个 "接口" 的 (v) 全都消耗完。
实际上，度数 (>3) 的情况，只需要先将多余的儿子内部完全对接起来即可，最后保留两个儿子即可。
代码和过程都比较精污……大概是我做麻烦了，赛后交了 (12) 发才过（
- B
太棒了，我不会初中数学。
由于元素两两不同，可以在条件两边同时乘上 ((a_i-a_j))，得到：
所以将每个 (a_i) 的 (a_i^4-a_icdot k) 算出来，丢到 map 里统计一下就完了。
- C
就这？
显然可以先将 (b) 排序。设 (f(S)=min_{iin S,jin S, i e j} left|b_{i}-b_{j} ight|)，我们要求的是 (sum_{i=0}^{infty} icdot sum_{Sin {1, 2, ldots, n}, |S|=k} left[f(S)=i ight])。它等价于 (sum_{i=1}^{infty}sum_{Sin {1, 2, ldots, n}, |S|=k} left[f(S)geq i ight])。
如果枚举 (i)，可以用前缀和、双指针优化 dp，在 (O(nk)) 内求出 (sum_{Sin {1, 2, ldots, n}, |S|=k} left[f(S)geq i ight])。注意到可能的最大的 (i) 不超过 (lfloorfrac{max b_i}{k-1} floor)，因此总的复杂度是 (O(nmax b_i))，可以通过。
确实，就这。
- D
就这？
原问题等价于求一个 (s)，使得 (sgeq max a_i)，并最小化 (sum_{i=1}^noperatorname{popcount}(s-a_i))，其中 (operatorname{popcount}(x)) 表示 (x) 在二进制下的 (1) 的个数。不难发现，如果所有 (s-a_i) 的最高位的 (1) 都相同，那么完全可以同时去掉这个 (1)。因此，设 (x) 表示 (max a_i) 的最高的 (1) 的位置，有 (s<2^{x+2})。
我们从低位向高位数位 dp，设 (f_{i, j}) 表示只考虑最低的 (i) 位，并将 (a) 按照最低的 (i) 位排序后，(sgeq a_j) 且 (s<a_{j+1}) 的情况下，在 (s-a_i) 最低的 (i) 位中的 (1) 的个数和的最小值（好像很拗口……）。
转移的时候，对于一个状态 (f_{i, j})，枚举 (s) 的第 (i+1) 位上是否是 (1)，可以将 (a) 序列分为 ((0/1, 0/1)) 的四部分：第 (i+1) 位上是否是 (1)；考虑前 (i) 位时，下标是否 (leq j)。将前 (i) 位 (s-a_u) 中减法的借位考虑进来，可以发现四个部分对应的 (a_u) 第 (i) 位分别是 (0, 1, 1, 2)。因此，如果 (s) 的第 (i+1) 位是 (1)，那么这一位上产生的贡献是第一和第四部分的元素个数，转移到的位置（(f_{i+1, j}) 中的 (j)）是前三部分元素个数和；否则，产生的贡献是第二和第三部分元素个数，转移到的位置是第一部分元素个数。注意枚举每个 (i) 时要按照第 (i) 位是否为 (1)，将 (a) “反归并” 排序。
确实，就这。
- E
就这？
对于这一类统计 “有多少种本质不同的染色” 的题目，一般都是从判断 “某种确定的染色是否合法” 入手。
首先注意到操作等价于给每个颜色都 (-1)，然后给某个颜色 (+k)，并且任意次操作后所有颜色总数不变。因此，设一共操作了 (x) 次，对于 (x_1 ot equiv x_2pmod k) 的情况，它们产生的结果必然不会相同（因为 (a_imod k) 的值不同）。
因此考虑枚举 (r=xmod k)。先判断是否存在至少一个操作序列至少操作了 (r) 次。将 (a) 排序后，显然按照 (a_1 ightarrow a_k) 的顺序操作最优。因此，如果 (a_i<i-1)，在操作第 (i-1) 次的时候必然会存在多个位置是 (0)，从而无法操作。这时候，我们发现，如果可以操作至少 (k) 次，那么只要按照 (a_1 ightarrow a_k) 的顺序复读，就可以无限地操作下去；否则，这个序列就最多只能操作 (r) 次。
对于能操作至少 (k) 次的，我们从 (r=0 ightarrow k-1) 枚举。最开始时，给每个位置分配 (a_imod k) 的权值，不难发现剩余的空闲权值 (s) 一定能被 (k) 整除，并且可以将 (frac{s}{k}) 在 (k) 个位置上任意分配。(r) 每次移动时，等于每个位置初始分配的权值减小了 (1)。这时候只需要把所有权值 (<0) 的位置再分配 (k) 的权值即可。由于操作可以持续无限次，任意一种分配方式都是合法的。
否则，我们仍然枚举 (r)，此时只需要模拟每一步如何操作即可。换句话说，对于每一步中新增的操作，我们不需要直接将它反映在序列上，而是记录新增了多少次操作。如果出现了 (a_i<0) 的情况，就将 (k) 的权值分配给 (a_i)。每一步中，空闲的操作都可以给 (k) 个位置任意分配。不难证明，上面枚举的方案都是合法的，且不重不漏。
确实，就这。（诶你是 (3200) 的题啊，给点面子好不好）