【省内训练2018-12-21】Connection - 代码先锋网

【省内训练2018-12-21】Connection - 代码先锋网

• 首先考虑某一种颜色，若该颜色在各连通块中的出现次数为 $\{x_1,x_2,...,x_m\}${x1​,x2​,...,xm​} ，则该颜色对答案的贡献应为 $\sum_{i=1}^{m}\sum_{j=i+1}^{m}x_i*x_j=\frac{(\sum_{i=1}^{m}x_i)^2-\sum_{i=1}^{m}x_i^2}{2}$∑i=1m​∑j=i+1m​xi​∗xj​=2(∑i=1m​xi​)2−∑i=1m​xi2​​ ，因此我们只需要考虑各连通块各颜色出现次数平方的和即可。
• 考虑一棵树的做法，显然直接启发式合并 $map$map 或是线段树合并即可计算每一棵子树中各颜色出现次数平方的和。
• 对原图建一棵圆方树，套用树的做法即可。
• 时间复杂度为 $O(M+NLog^2N)$O(M+NLog2N) 或 $O(M+NLogN)$O(M+NLogN) 。

Read full article from 【省内训练2018-12-21】Connection - 代码先锋网