记录编号	86935	评测结果	AAAAAAAAAA
题目名称	丢失的家	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2014-01-29 10:41:11	内存使用	0.34 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
#include<set>
using namespace std;
const int SIZEN=1010;
int N;
int father[SIZEN]={0};
bool worm[SIZEN]={0};
vector<int> son[SIZEN];
int leaves[SIZEN]={0};//子树上的叶子个数
int success[SIZEN]={0};//在本树上的的期望和
int failure[SIZEN]={0};//不在本树上的搜索步数
bool cmp(int u,int v){//u放前面比v放前面优秀的条件
	return (failure[u]+2)*leaves[v]<(failure[v]+2)*leaves[u];
}
void DP(int u){//对u这个结点进行Tree DP
	if(son[u].size()==0){//叶子节点
		success[u]=failure[u]=0;
		leaves[u]=1;
		return;
	}
	for(int i=0;i<son[u].size();i++) DP(son[u][i]);//求解子问题
	for(int i=0;i<son[u].size();i++) leaves[u]+=leaves[son[u][i]];//统计叶子个数
	sort(son[u].begin(),son[u].end(),cmp);
	for(int i=0;i<son[u].size();i++){
		success[u]+=(failure[u]+1)*leaves[son[u][i]]+success[son[u][i]];
		failure[u]+=failure[son[u][i]]+2;
	}
	if(worm[u]) failure[u]=0;//如果有蠕虫指路,failure就不用查找了
}
void work(void){
	DP(1);
	double ans=(success[1]+0.0)/(leaves[1]+0.0);
	printf("%.4lf\n",ans);
}
bool read(void){
	scanf("%d",&N);
	if(!N) return false;
	//clear
	memset(father,0,sizeof(father));
	memset(worm,0,sizeof(worm));
	for(int i=1;i<=N;i++) son[i].clear();
	memset(leaves,0,sizeof(leaves));
	memset(success,0,sizeof(success));
	memset(failure,0,sizeof(failure));
	//read
	char ch;
	for(int i=1;i<=N;i++){
		scanf("%d %c",&father[i],&ch);
		worm[i]=(ch=='Y'?1:0);
		if(father[i]!=-1) son[father[i]].push_back(i);
	}
	return true;
}
int main(){
	freopen("losthouse.in","r",stdin);
	freopen("losthouse.out","w",stdout);
	//while(read()) work();
	//POJ上的格式是多组数据
	read();
	work();
	return 0;
}