Readme

2440.Create-Components-With-Same-Value

假设我们想要把这张图平均分成k份，那么每一份联通块的元素和s我们是知道的。假设我们可以实现这样的拆分，从图中我们显然可以发现，每一份符合条件的联通块必然可以从外往内一点一点剥离下来。这就提示我们可以用拓扑排序的方法。我们记录sum[i]表示从外往内“剥洋葱”的过程中，剥到节点i时所对应的“子树”的节点元素之和。

1. 如果sum[i]==s，那么说明这棵子树就是符合条件的一个联通块，我们就彻底剥离，节点i不传递信息给它的上级。
2. 如果sum[i]<s，那么这棵子树还不能独立，必须把sum[i]传递给节点i的上一级节点，以期待在一棵更大的子树里恰好凑成给一个合法的联通块。
3. 如果sum[i]>s，那么说明这棵子树的元素和太大了，不能构成一个合法的联通块，终止基于s的进一步的尝试。

我们重复上述剥洋葱的过程，如果把所有节点都剥完，依然没有报错，那么说明我们恰好把整张图剥离成了一个个元素和为s的子树。

显然，拓扑排序的复杂度是o(N)。那么我们需要尝试多少个s呢？s的个数应该是total的因子个数，即sqrt(total)。其中total是整张图的元素之和。综上，总的时间复杂度恰好就是1e6级别。