树形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 <stdio.h>
#include <algorithm>
#include <string.h>
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<scnt;i++)
{
dp[u][1]+=dp[sss[i]][1]+(temp+1)*num[sss[i]];
temp+=dp[sss[i]][0]+2;
}
}
}
int main()
{
while(scanf("%d",&n),n)
{
cnt=0;
memset(exist,false,sizeof(exist));
memset(head,-1,sizeof(head));
scanf("%d%s",&x,s);
for(int i=2; i<=n; i++)
{
scanf("%d%s",&x,s);
if(s[0]=='Y')exist[i]=true;
addedge(x,i);
}
dfs(1);
printf("%.4lf
",((double)dp[1][1])/(double)num[1]);
}
return 0;
}