题意：有一棵N的点的树，开始的时候蜗牛在1号结点，它不知道它的家在哪个叶子结点，树上的有些结点有虫虫，虫虫会告诉你，你的家是否在以它所在结点为根的子树上，现在需要你规划走的方案，使得找到哪个叶子结点才是家的所走路径的期望最小。
思路：这里的路径规划，必定是有迹可循的，譬如说，我们现在有两棵子树A、B；如果走A结点，而不是走B结点，说明的是先走A再走B的期望就要更小，反之亦然。
走A子树的期望：“家在A子树上的距离” *
+ （“家不在A子树上的距离” + “家在B子树上的距离”） *
。
走B子树的期望：“家在B子树上的距离” *
+ （“家不在B子树上的距离” + “家在A子树上的距离”） *
。
“”代表家在A子树的概率；
“”表示家在B子树的概率。
若走A比走B期望值更小，则说明
将等式带入，化简，可以求得
由
有：“家不在A子树上的距离” * - “家不在B子树上的距离” *
< 0。
也就是：“家不在A子树上的距离” * < “家不在B子树上的距离” *
。
此时，我们走A子树。
怎么计算“家不在X子树上的距离”呢？
如果说当前点是u，下一个点是v，有u->v的这样的边，如果说v点上有虫虫，那么也就是说以v为根的子树要么就是有家的，哟要么就是没家的，有家的话就不用算了，没家的话，其实直接返回就是了；反之，v点上没有虫虫，那么，我们就是需要继承v点到它下面子树的“家不在V子树上的距离”了，并且“+2”是为了返回到u点。
知道这个之后，我们就可以根据之前求出来的不等式来进行sort了，期间可以用vector存点，因为点的总数是固定的，但是呢每个点的下一个结点有多少个确实未知的。
剩下的就是求总距离和了，然后用总距离和去除以叶子结点的数量，就是期望值了。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e3 + 7;
int N, head[maxN], cnt, siz[maxN];
bool lives[maxN];
struct Eddge
{
int nex, to;
Eddge(int a=-1, int b=0):nex(a), to(b) {}
}edge[maxN];
inline void addEddge(int u, int v)
{
edge[cnt] = Eddge(head[u], v);
head[u] = cnt++;
}
ll dis[maxN], dp[maxN];
inline bool cmp(int e1, int e2) { return (dis[e1] + 2) * siz[e2] < (dis[e2] + 2) * siz[e1]; }
void dfs(int u)
{
dis[u] = dp[u] = siz[u] = 0;
if(!~head[u]) { siz[u] = 1; return; }
vector<int> vt; int len = 0;
for(int i=head[u], v; ~i; i=edge[i].nex)
{
v = edge[i].to;
dfs(v);
vt.push_back(v); len++;
siz[u] += siz[v];
if(!lives[u]) dis[u] += dis[v] + 2;
}
sort(vt.begin(), vt.end(), cmp);
ll tmp = 0;
for(int i=0; i<len; i++)
{
dp[u] += dp[vt[i]] + siz[vt[i]] + tmp * siz[vt[i]];
tmp += dis[vt[i]] + 2;
}
}
inline void init()
{
cnt = 0;
for(int i=1; i<=N; i++) { head[i] = -1; lives[i] = false; }
}
int main()
{
while(scanf("%d", &N) && N)
{
init();
int pre; char ch[3];
for(int i=1; i<=N; i++)
{
scanf("%d%s", &pre, ch);
if(!~pre) continue;
addEddge(pre, i);
lives[i] = ch[0] == 'Y';
}
dfs(1);
printf("%.4f\n", 1. * dp[1] / siz[1]);
}
return 0;
}