連MAZE這種題我都做了好久我弱爆了……

HDU4035,11號網絡賽的MAZE,這道遞推因為我把幾個區域變量【優化】到了全局結果一直WA,然後我就禿了……
算法:
這個禿雖然是個無根樹,但是由於樹根是確定的了,所以實質上就是個有根樹.設e[i]是以點i為子樹走出迷宮所需的數學期望,那麼可以【得知】,對於任意一個e[i],其結果一定是一個關於e[1],e[fa[i]]的一次多項式,即我們這裡可以設e[i]=r[i]*e[1]+x[i]*e[fa[i]]+a[i].那麼對於任意一個點i,都有e[i]=k[i]*e[1]+tmp[i]*(e[fa[i]]+sum(e[j],j為i的兒子)+1),其中tmp[i]=(1-k[i]-e[i])/cnt[i],cnt[i]即點i的度..又因為e[fa[j]]=e[i],j是i的兒子,所以,我們可以發現,e[i]中的三個係數r[i],x[i]和a[i]都可以由i的兒子節點們給遞推出來.這樣遞推到最後,這種會發現e[1]=r[1]*e[1]+a[1],此時就相當於解一個關於e[1]的一元一次方程,解出來即可.
source code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define maxn 10010
#define eps (1e-10)
#define clr(a) memset(a,0,sizeof(a))
struct edge{
  int vt,next;
};
edge e[maxn*5];
double K[maxn],E[maxn],r[maxn],x[maxn],a[maxn],tmp[maxn];
int fa[maxn],cnt[maxn],st[maxn];
bool vis[maxn];
int testcase,n,tot,p,q;
double ttmp;
bool flag;
int sig(double x){
  return (x>eps)-(x<-eps);
}
int addedge(int u,int v){
  e[++tot].vt=v,e[tot].next=st[u],st[u]=tot;
  return 0;
}
int dfs1(int u){
  cnt[u]=0;
  for(int i=st[u];i!=0;i=e[i].next){
    ++cnt[u];
    if(!vis[e[i].vt])
       vis[e[i].vt]=true,fa[e[i].vt]=u,dfs1(e[i].vt);
  }
  tmp[u]=(1-K[u]-E[u])/cnt[u];
  return 0;
}
int dfs2(int u){
  if(vis[u])
    return 0;
  vis[u]=true;
  r[u]=x[u]=a[u]=0;
  double R=0,X=0,A=cnt[u];
  for(int i=st[u];i!=0;i=e[i].next){
    if(e[i].vt==fa[u])
      continue;
    dfs2(e[i].vt);
    R+=r[e[i].vt],X+=x[e[i].vt],A+=a[e[i].vt];
  }
  R*=tmp[u],X*=tmp[u],A*=tmp[u];
  if(sig(ttmp=1-X)==0)
    flag=false;
  if(flag)
    r[u]=(K[u]+R)/ttmp,x[u]=tmp[u]/ttmp,a[u]=A/ttmp;
  return 0;
}
int main(){
  scanf("%d",&testcase);
  for(int ttestcase=1;ttestcase<=testcase;++ttestcase){
    printf("Case %d: ",ttestcase);
    clr(st);
    scanf("%d",&n);
    tot=0;
    for(int i=1;i<n;i++){
      scanf("%d%d",&p,&q);
      addedge(p,q),addedge(q,p);
    }
    for(int i=1;i<=n;i++){
      scanf("%lf%lf",K+i,E+i);
      K[i]/=100.0,E[i]/=100.0;
    }
    flag=true;
    clr(vis),vis[1]=true;
    dfs1(1);
    clr(vis),vis[1]=true;
    for(int i=2;i<=n;i++)
      dfs2(i);
    if(!flag){
      printf("impossible\n");
      continue;
    }
    double X=0,A=0;
    for(int i=st[1];i!=0;i=e[i].next)
      X+=x[e[i].vt]+r[e[i].vt],A+=a[e[i].vt]+1;
    X*=tmp[1],A*=tmp[1];
    if(sig(ttmp=1-X)==0){
      printf("impossible\n");
      continue;
    }
    printf("%.6lf\n",A/ttmp);
  }
  return 0;
}