Codeforces 235D: Graph Game
1. 题目大意
有一个\(n\)个点\(n\)条边的无向连通图\(T\)，定义一个随机点分治过程\( solve(T) \)如下：
1. 令变量\(totalCost \, = \, totalCost \, + \, | T | \)；
2. 在\(T\)中随机选取一个点\(x\)，所有点被选取的概率相同；
3. 从\(T\)中删除点\(x\)；
4. \(T\)被分成了若干个连通子图，对于每一个子图\(S\)，递归调用\( solve(S) \)。
其中变量\(totalCost\)的初始值为0。
求算法结束后\(totalCost\)的期望值。
2. 数据范围
\(3 \le n \le 3000\)
3. 题解
首先“随机点分治”就相当于给每个点随机生成一个不重复的\(rank\)表示删除的次序。
先考虑树的情况。对于任意一个点对\( (u, v) \)，如果在删除\(u\)时，\(u\)到\(v\)的路径上其他点都没被删除（即\(u\)的\(rank\)是\(u\)到\(v\)路径上所有点中最小的），那么这个点对会对\(totalCost\)产生1的贡献。因此我们直接枚举点对计算答案即可。
实际上题目给出的并不是树，而是环套树，那么\( (u, v) \)之间可能存在两条路径。对于这种情况，容易想到存在贡献的条件就是\(u\)的\(rank\)是\(u\)到\(v\)的所有路径中至少一条中最小的，用简单的容斥算一下就可以了。否则只需要套用树上的方法。
4. 时空复杂度
时间复杂度：\( O( n^2 ) \)
空间复杂度：\( O( n ) \)
5. 代码
代码在这里。
