这道题站在每个位置上都会有三种状态

死亡回到起点:k[i]

找到出口结束 e[i]

原地不动 p[i]

k[i]+e[i]+p[i] =1;

 

因为只给了n-1条路把所有都连接在一起，那么我们可以自然的把这张图看成一个树型结构

根据作为父亲节点和叶子节点作为区分

进行推导

 

详情可参考:

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 #define N 10005 6 #define del 1e-10 7 vector 
        
          G[N]; 8 double A[N],B[N],C[N],k[N],e[N],p[N]; 9 int n;10 bool solve(int u,int fa)11 {12     A[u] = k[u];13     B[u] = p[u] / G[u].size();14     C[u] = p[u];15 16     if(G[u].size() == 1 && fa!=0)17         return true;18 19     double tmp = 0;20     for(int i=0;i