树形DP的第一题，看了好几天才明确....

题目大意：

有一仅仅蜗牛爬上某个树枝末睡着之后从树上掉下来,发现后面的"房子"却丢在了树上面, 如今这仅仅蜗牛要求寻找它的房子,它又得从树根開始爬起去找房子。如今要求一条路径使得其找到房子所要爬行的期望距离最小。

解题思路：

影响期望的因素有树的结构，分支节点上是否有虫子，蜗牛走的路线。

对于随意一棵子树来说树的结构，分支节点上是否有虫子是一定的。我们仅仅须要为它设计一个路线使蜗牛在这上面寻找的期望值最小。递归须要设计整棵树的路线。

设一棵树有两个子树A,B。Pa是房子在A子树上的概率，Pb是房子在B子树上的概率。

先走A子树寻找房子的期望是：

【在A子树上找到房子的路程】*Pa+（【没有在A子树上找到房子的路程（固定的一个值）】+【在B子树上找到房子的路程】）*Pb。

先走B子树寻找房子的期望是：

【在B子树上找到房子的路程】*Pb+（【没有在B子树上找到房子的路程（固定的一个值）】+【在A子树上找到房子的路程】）*Pa。

若这两个值做比較的话，能够化简为：

【没有在A子树上找到房子的路程（固定的一个值）】*pb同【没有在B子树上找到房子的路程（固定的一个值）】*pa相比較。

Pa=A子树上的叶子节点数/全部的叶子节点数。Pb也是如此。

通过排序就能够设计出在树上的寻找路径了。

以下是代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;struct node{    int to,next;} edge[1005];int head[1005],cnt,n,x,dp[1005][2],num[1005];bool exist[1005];char s[3];void addedge(int u,int v){    edge[cnt].to=v;    edge[cnt].next=head[u];    head[u]=cnt++;}int cmp(int a ,int b){    return (dp[a][0]+2)*num[b]<(dp[b][0]+2)*num[a];}void dfs(int u){    int p=head[u];    dp[u][0]=0;    dp[u][1]=0;    num[u]=0;    if(p==-1)    {        num[u]++;    }    else    {        int scnt=0,sss[10];        while(p!=-1)        {            sss[scnt++]=edge[p].to;            dfs(edge[p].to);            num[u]+=num[edge[p].to];            if(!exist[u])dp[u][0]+=dp[edge[p].to][0]+2;            p=edge[p].next;        }        sort(sss,sss+scnt,cmp);        int temp=0;        for(int i=0;i