牛客暑假多校训练赛第九场
今日又是自闭场，一道“假题”研究了三个小时。“假题”很简单，就是折半枚举，不想做了。
比赛最后一小时开始看E题，E题也不算难，但是没搞出来（我太弱了），吃完饭继续做E题，还是不行。看了题解之后，发现我的思路是走不通的，唉……1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101// 不能每次合并后计算可行总数，太繁琐，时间上也太慢
// 可行做法 ：计算出初始方案数量，之后每次合并时减少
// 遗憾，比赛时没想出来，补题时也没想到…………
// #pragma GCC optimize(2)
using namespace std;
const int maxn = 110000;
int maxm;
int u[maxn];
int sz[maxn];
typedef long long ll;
ll solve4(int x) //计算组合数4
{
__int128 r = 1;
r = r * (x - 3) * (x - 2) * (x - 1) * x / 24;
ll re = (ll)r;
return re;
}
void makeset()
{
for (int i = 1; i <= maxm; i++)
{
u[i] = i;
sz[i] = 1;
}
}
int Find(int x) //查询该数属于哪一个集合
{
if (x != u[x]) //路径压缩后的写法
{
u[x] = Find(u[x]);
}
return u[x];
}
int Union(int a1, int a2)
{
int p1 = Find(a1);
int p2 = Find(a2);
if (p1 == p2) // 二者属于一个集合
return 0;
if (sz[p1] > sz[p2])
swap(p1, p2);
u[p1] = p2;
sz[p2] += sz[p1];
return 1;
}
ll l2(int x)
{
ll r = 1;
r = r * x * (x - 1) >> 1;
return r;
}
int main()
{
int n, m, a, b;
ll zz = 0;
scanf("%d%d", &n, &m);
// printf("%d\n",m);
maxm = n;
int num = n;
makeset();
if (n >= 4)
{
ll ans = solve4(n); //集合大小如何求？？在合并的函数里处理
printf("%lld\n", ans);
while (m--)
{
scanf("%d%d", &a, &b);
int size_a = sz[Find(a)], size_b = sz[Find(b)];
int na = size_a, nb = size_b;
if (Find(a) != Find(b))
{
num--;
}
else
{
printf("%lld\n", ans);
continue;
}
if (num < 4)
{
printf("0\n");
continue;
}
int sum = n - size_a - size_b; // 除了这个集之外的数字数量
zz = zz - l2(na) - l2(nb);//
ll cha = na * nb * (l2(sum) - zz);
ans -= cha;
zz += l2(na + nb);//加上在该集合中的任选2个的方案数
printf("%lld\n", ans);
Union(a,b);
}
}
else
{
for (int i = 0; i < m; i++)
puts("0");
}
return 0;
}