题目描述

思路分析

    从一个图中最少去除多少条边可以使得图中无环。明显并查集入门题，我们只需要维护每个端点的集合，如果两个端点在同一个集合，则说明出现环，则当前边不进行并查集的合并，并且计数。

代码展示

因为涉及到区间加操作，一开始考虑差分数组，最终情况就是全部数为00。这样每次操作就只修改两个数，且观察到其下标对 k取模都是相同的。 然后考虑对原数组求一遍操作影响，看看子数组能否利用原数组的信息，思考了下感觉可行但代码复杂。

后来又退回思考原数组，因为是连续的区间加，假设sum[i]表示下标对 k取模为 i的所有数的和。那每次操作就是将 sum的所有数都 +x。那最终为 0的充分条件就是 sum的所有数都是一样的。反过来，也是必要条件。

因此对于每组询问，统计该序列的下标对k取模的所有数的和，看看是否为同一个数即可。

预处理原数组的下标取模前缀和，每组询问就两个前缀和相减就得到该区间的下标取模前缀和。因为k只有 10，所以每次询问的复杂度就是 O(k)