题意

有一颗树n个结点n-1条边，根结点为1
对于在点i下一步有3种情况：
1：被杀死回到点1 --- 概率为ki
2：找到出口退出----慨率为ei
3：等概率的沿着边进入下一个点
求从点1开始到退出的平均需要走的边数

Solution

1:i为叶子节点

$$E_{i}=k_{i}\times{E_{1}}+(1-k_{i}-e_{i})\times{E_{father_{i}}}+1-k_{i}-e_{i}{\small}$$

2:i非叶子节点

m为与i节点相连的边数

$$E_{i}=k_{i}\times{E_{1}}+\frac{1-k_{i}-e_{i}}{m}\times{E_{father_{i}}}+\frac{1-k_{i}-e_{i}}{m}\times{\sum_{j\in{son_{i}}}E_{j}}+1-k_{i}-e_{i}$$

然后我们发现所有的$E_{i}$都可以表示成$A{i}\times{E_{1}}+B_{i}\times{E_{father_{i}}}+C_{i}$的形式

于是i为叶子节点时

$$A_{i}=k_{i}$$
$$B_{i}=1-k_{i}-e_{i}$$
$$C_{i}=1-k_{i}-e_{i}$$

i非叶子节点时

$$\sum_{j\in{son_{i}}}E_{j}=\sum_{j\in{son_{i}}}A_{j}\times{E_{1}}+B_{j}\times{E_{i}}+C_{j}$$
$$(1-\frac{1-k_{i}-e_{i}}{m}\times{\sum_{j\in{son_{i}}}}B_{j})\times{E_{i}}=(k_{i}+\frac{1-k_{i}-e_{i}}{m}\times{\sum_{j\in{son_{i}}}}A_{j})\times{E_{1}}+\frac{1-k_{i}-e_{i}}{m}\times{E_{father_{i}}}+1-k_{i}-e_{i}+\frac{1-k_{i}-e_{i}}{m}\times{\sum_{j\in{son_{i}}}}C_{j}$$
$$A_{i}=\frac{k_{i}+\frac{1-k_{i}-e_{i}}{m}\times{\sum_{j\in{son_{i}}}}A_{j}}{1-\frac{1-k_{i}-e_{i}}{m}\times{\sum_{j\in{son_{i}}}}B_{j}}$$
$$B_{i}=\frac{\frac{1-k_{i}-e{i}}{m}}{{1-\frac{1-k_{i}-e_{i}}{m}\times{\sum_{j\in{son_{i}}}}B_{j}}}$$
$$C_{i}=\frac{1-k_{i}-e_{i}+\frac{1-k_{i}-e_{i}}{m}\times{\sum_{j\in{son_{i}}}}C_{j}}{1-\frac{1-k_{i}-e_{i}}{m}\times{\sum_{j\in{son_{i}}}}B_{j}}$$
从叶子节点往上递推即可

代码戳这里

#include<iostream>//马尔科夫链
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int N=10005;
const double eps=1e-10;
double A[N],B[N],C[N],k[N],e[N];
vector<int>edge[N];
void dfs(int u,int f){
    double a=0.0,b=0.0,c=0.0;
    int m=0;
    for(int i=0;i<edge[u].size();++i){
        int v=edge[u][i];
        if(v==f)  continue;
        dfs(v,u);
        a+=A[v];
        b+=B[v];
        c+=C[v];
        ++m;
    }
    if(f)   ++m;
    double p=(1-k[u]-e[u])/m;
    A[u]=(k[u]+p*a)/(1-p*b);
    B[u]=p/(1-p*b);
    C[u]=(1-k[u]-e[u]+p*c)/(1-p*b);
}
int main(){
    int T,n;
    scanf("%d",&T);
    for(int tt=1;tt<=T;++tt){
        printf("Case %d: ",tt);
        scanf("%d",&n);
        for(int i=1;i<N;++i) edge[i].clear(),A[i]=0,B[i]=0,C[i]=0;
        for(int i=1,x,y;i<n;++i){
            scanf("%d%d",&x,&y);
            edge[x].push_back(y);
            edge[y].push_back(x);
        }
        for(int i=1;i<=n;++i)    scanf("%lf%lf",&k[i],&e[i]),k[i]/=100.0,e[i]/=100.0;
        dfs(1,0);
        if(fabs(1-A[1])<eps)    printf("impossible\n");
        else printf("%.6lf\n",C[1]/(1-A[1]));
    }
    return 0;
}