1731.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1731 on 2006-05-26 at 09:25:51 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int FN = 1024;

class Fork {
public:
	int brn, nh, yh;
	bool worm;
	vector<int> child;
	bool operator <(const Fork& f) const { return nh*f.brn < f.nh*brn; }
	void clear() { child.clear(); brn = nh = yh = 0; }
	void find();
};
Fork f[FN];
bool cmp(const int a, const int b) { return f[a] < f[b]; }
void Fork::find() {
	if(child.size() == 0) { brn = 1; nh = 2; return; }
	vector<int>::iterator i;
	for(i = child.begin(); i != child.end(); i++) {
		f[*i].find();
		brn += f[*i].brn;
	}
	sort(child.begin(), child.end(), cmp);
	for(i = child.begin(); i != child.end(); i++) {
		yh += f[*i].brn*(nh+1)+f[*i].yh;
		nh += f[*i].nh;
	}
	if(worm) nh = 0;
	nh += 2;
}

int main()
{
	int n, i;

	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) f[i].clear();
		for(i = 0; i < n; i++) {
			int prt; char worm;
			scanf("%d %c", &prt, &worm);
			if(prt > 0) f[prt-1].child.push_back(i);
			f[i].worm = (worm == 'Y');
		}
		f[0].find();
		printf("%.4lf\n", f[0].yh*1.0/f[0].brn);
	}
	
	return 0;
}