求助为什么总点数是k
查看原帖
求助为什么总点数是k
560700
ZnPdCo楼主2024/4/4 21:33

我看题解中:

团的大小并不好计算,但是我们是容易计算团外面的点数的,于是简单容斥一步就可以了。对于团外面的点数,我们考虑连通块往外连的每一条不合法链,设连通块外的子树为 a,连通块内的子树为 b,那么我们让所有的牛全部填满子树 b,则多出来的点就是这条不合法链方向的不在连通块内的点,这些点的数量等于 k−(b−1)……拿 k 减去它就是团的点数

这里说团中点数为总点数减去团外面的点数。但是总点数为什么为 kk,不太清楚原因。

2024/4/4 21:33
加载中...