Team-Building

· · 题解

有 n 个学生，有 k 个学习小组。m 个二元组 (a_i,b_i)。

一个二元组 (x,y) 的权值 w(x,y) 表示是否存在一个划分：(S,T)，使得 S 中每个二元组和 T 中每个二元组都没有在 m 个二元组中出现过。

求 \sum w(x,y)。

首先我们发现，这个划分等价于判断这个图是否是二分图。也就是是否有奇环。

此时，我们考虑原先 m 条边生成的图 G，这个二元组一定不能完整包含一个奇环。

不妨容斥一下，去数完整包含一个奇环的二元组。

首先把已经包含奇环的组处理出来。

我们枚举每个小组，试图计算有有多少个包含它的二元组中完整包含奇环。

首先分为两种，一种是枚举的小组已经包含了一个奇数环的，这个时候，所有与他相关的都是包含奇环的。

否则，如果另一边是一个包含奇环的小组，那么也包含一个奇环。

否则，则一定要有一个中间的边使得他们之间构成了奇环。枚举即可。