题解：CF235D Graph Game

· · 题解

好题啊。基本把期望线性性玩明白了。

利用期望线性性，首先可以拆贡献。要计算“某个点在点分治过程中被遍历的期望次数”。所有点分别计算后求和就是答案。

然后可以手玩这个分治过程，假设要计算的点为 i，从 i 的视角观察，把它定为“根”。然后就会发现，按照分治过程，等概率在 i 所在的联通块内选一个点，然后把它删掉，重复直至 i 被删掉，这个过程是和原点分治是一样的。所以一个点的贡献可以转化为进行上述操作的期望步数。

要解决如上问题，依然可以拆贡献。要计算“x 点在操作中被删掉次数的期望（也就是被删的概率）”

以下图情况（x 到 i 间经过基环）解决该问题：

首先我们构造一个“操作序列”，是一个 1 \sim n 的排列。按顺序在原基环树上删点，要是不合法操作就直接忽略。容易发现操作序列中合法点的部分与实际删点的方案一一对应，并合法点部分出现的概率等于实际删点方案的概率。

具体来说，在第 j 次（共 cnt 次）删点时，记除自己外，被删掉（与 i 断开）的点数为 del_j。我们可以在当前操作序列最靠左的空位上填写点的编号，把填上后面剩余的空位选择 del_j 个用这些被断开的点任意排列后补齐。这样同一个删点方案所对应的排列出现的概率即为

\dfrac{\prod_{s=1}^{cnt}A_{n-s-\sum_{t=1}^{s-1}del_t}^{del_s}}{n!} = \dfrac{(n-1) \times (n-2) \times ... \times (n-del_1) \times (n-del_1-2) \times ... \times (n-del_1-del_2-1) \times ...}{n!}

消完后即得到实际操作的概率。

欸？好像有道题也是这么个证法。

回到图上，D 部分是不在环上的点 + 进入和走出环上的点，在删点过程中，他们中一个被删了，x 不能被删，所以在操作序列上他们必须在 x 点的后面，x 才能合法地被删除。同理，a1 和 a2 部分是 x 到 i 环上可能的两条路径，则需要至少一个部分在操作序列上完全在点 x 的后面。经过简单的计算+容斥可得最终的答案为 \frac1{D+a1} + \frac1{D+a2} - \frac1{D+a1+a2}。

然后其他情况比这个简单，也是这么推的。

然后这道题就做完了。

时间复杂度 O(n^2)

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> vec[3002];
int du[3002];
queue<int> q;
bool incir[3002];
int cirtot;
void forcir(){
    for(int i=1;i<=n;i++) incir[i] = 1;
    cirtot = n;
    for(int i=1;i<=n;i++) if(du[i] == 1) q.push(i);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        incir[u] = 0;
        cirtot--;
        for(int i=0;i<vec[u].size();i++){
            int v = vec[u][i];
            du[v]--;
            if(du[v] == 1){
                q.push(v);
            }
        }
    }
}

int dep[3002], a[3002];
bool vis[3002];
double solve(int pos,int fa){
    //cout << pos <<endl;
    double ret = 0;
    if(!incir[pos]) dep[pos] = dep[fa] + 1, a[pos] = a[fa];
    else dep[pos] = dep[fa], a[pos] = a[fa] + 1;
    double S = dep[pos]+min(a[pos],2);
    if(a[pos] > 2 && cirtot - a[pos] > 0) ret += 1.0 / (S + a[pos]-2) + 1.0 / (S + cirtot-a[pos]) - 1.0 / (S + cirtot-2);
    else ret += 1.0 / S;
    for(int i=0;i<vec[pos].size();i++){
        int v = vec[pos][i];
        if(vis[v]) continue;
        vis[v] = 1, ret += solve(v,pos);
    }
    return ret;
}

int main(){

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int u, v;
        scanf("%d%d",&u,&v);
        u++, v++;
        vec[u].push_back(v);
        vec[v].push_back(u);
        du[u]++, du[v]++;
    }
    forcir();
    //for(int i=1;i<=n;i++) cout << incir[i] << ' ';
    //cout << endl;

    double Ans = 0;
    for(int i=1;i<=n;i++){
        //cout << i << endl;
        for(int j=1;j<=n;j++) vis[j] = 0;
        vis[i] = 1, Ans += solve(i,0);
    }

    printf("%.10f",Ans);

    return 0;
}