题意:\(n(n<=1000)\)个节点的树,蜗牛把壳落在了一个树叶上，壳在每一个树叶上的概率是相同的.现在蜗牛从树根开始爬，在树杈中可能会有毛毛虫，毛毛虫会告诉蜗牛壳是否在这个点的子树中.每个树枝的长度为1，求蜗牛最终能找到壳需要爬行的距离的期望值最小是多少.
分析:本人题解结合了博客一的讲解和博客二的实现.
期望值=\(\sum\)蜗牛到第i个叶子的距离\(*\)壳在第i个叶子上的概率= 蜗牛到所有叶子节点的距离的和/叶子节点数.于是题目转化为了,我们要求一个序列，按这个序列到达每一个叶子节点的距离的和是最小的.
设节点x,y都是节点u的子节点,假设壳在u的子树中(即壳在子树x或者子树y中).那么我们有两种选择:
选择一:先走x,再走y.则期望值=在x上找到壳的期望步数壳在x上的概率+(在x上寻找失败后由x返回u的步数+在y上找到壳的期望步数)壳在y上的概率
选择二:先走y,再走x.则期望值=在y上找到壳的期望步数壳在y上的概率+(在y上寻找失败后由y返回u的步数+在x上找到壳的期望步数)壳在x上的概率
拆开括号，可以发现两个选择，即两个式子只有一个地方不同，选择一是 在x上寻找失败后由x返回u的步数壳在y的概率;选择二是 在y上寻找失败后由y返回u的步数壳在x上的概率
所以我们只要依据这个从小到大排序，就能得到我们是先走x，还是先走y了．
以上是关于如何走的讨论,可以说是本题的核心部分.下面讲如何实现.
设\(size[u]\)表示以u为根的子树中叶子节点的个数,\(su[u]\)表示在以u为根的子树中找到壳期望走的距离(1为根节点，\(su[1]/size[1]\)即为最终答案),设\(fail[u]\)表示在以u为根的子树中，遍历整个子树都没有找到壳又返回x节点期望走的距离.
设v是u的子节点,dfs回溯的时候\(size[u]+=size[v]\)就可以处理出size数组了.\(su[u]+=(fail[u]+1)*size[v]+su[v]\)表示当前考虑u的子树,之前遍历的子树一直没找到壳,现在走进了子树v找到了壳;\(fail[u]+= fail[v]+2\)表示遍历了子树v没有找到壳,所以返回节点u.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1005;
int bj[N],size[N],su[N],fail[N];
vector<int>q[N];
inline bool cmp(int x,int y){
return (fail[x]+2)*size[y]<(fail[y]+2)*size[x];
}
inline void dfs(int u){
if(!q[u].size()){//如果是叶子节点
size[u]=1;
su[u]=0;fail[u]=0;
return;
}
for(int i=0;i<q[u].size();++i){//遍历子节点
int v=q[u][i];
dfs(v);size[u]+=size[v];
}
sort(q[u].begin(),q[u].end(),cmp);//按照上面分析的那样排序
for(int i=0;i<q[u].size();++i){
int v=q[u][i];
su[u]+=(fail[u]+1)*size[v]+su[v];
fail[u]+=fail[v]+2;
}
if(bj[u])fail[u]=0;
//别忘了!!!如果有毛毛虫,就不会出现 走进去 又没找到壳 的情况
}
int main(){
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
while(1){
int n=read();if(!n)break;
for(int i=1;i<=n;++i){
bj[i]=0;size[i]=0;
su[i]=0;fail[i]=0;
q[i].clear();
}//多组数据初始化
int x=read();char ch;cin>>ch;//第一组没用
for(int i=2;i<=n;++i){
x=read();cin>>ch;
if(ch=='Y')bj[i]=1;//如果有毛毛虫,打个标记
q[x].push_back(i);//直接vector存图
}
dfs(1);printf("%.4f\n",1.0*su[1]/size[1]);
}
return 0;
}