CF985G Team Players解题报告

解题报告

---

CF985G Team Players解题报告：

题意

给定 $n$ 个点 $m$ 条边的一张图，定义一个三元组 $(i,j,k)$ 是合法的当且仅当其内部没有一条边，定义其贡献为 $ai+bj+ck(i<j<k)$ （$a,b,c$ 为给定的常数），求所有合法三元组的贡献和。（$3\leqslant n\leqslant 2\times 10^5,0\leqslant m\leqslant 2\times10^5$）

分析

比较有意思的题。

由于没有边相连这种信息不好处理，考虑正难则反，利用其它的值算出 $k_0$，设 $k_0$ 为没有边的三元组贡献和， $k_1$ 为恰好有一条边的三元组贡献和， $k_2,k_3$ 类似。

直接枚举每一个三元组，可以算出

$$k_0+k_1+k_2+k_3=\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j+1}^n ai+bj+ck$$

这个东西计算有一种简单做法，求三遍后缀和，复杂度是 $O(n)$。

直接枚举每一条边和一个单点，可以算出（$E$为边集）

$$k_1+2k_2+3k_3=\sum_{(x,y)\in E\ x<y}(\sum_{i=1}^{x-1}ai+bx+cy)+(\sum_{i=x+1}^{y-1}ax+bi+cy)+(\sum_{i=y+1}^n ax+by+ci)$$

这个东西随便拆一下求和式就好了，复杂度 $O(m)$。

直接枚举每一个三元链，可以算出

$$k_2+3k_3=\sum_{(x,y)\in E}\sum_{(y,z)\in E}$$

直接枚举每一个三元环，可以算出

代码