丢失的家

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file losthouse.in Output file losthouse.out

【题目描述】

一天,一只蜗牛爬到了一棵大树上,它爬呀爬,最终爬到了树梢。它从来没有从这么高的地方向下看过,这真是一种新奇的感受!但由于爬了这么长时间,它已经很累了,很快便睡着了。当它醒来的时候,发现发生了一件不可思议的事情——它发现自己躺在一片草地上,并且自己原来背着的壳(英文原题中为house,这也是试题名称的由来——译者注)消失了!它马上明白了自己是在睡觉的时候从树梢上掉下来的!它确信自己的壳一定仍然在它刚才睡觉的树梢上。这只蜗牛开始重新爬树,因为它离开了壳就无法生存。

当到达树的第一个分叉时,它忧桑地发现自己想不起来之前爬过的路线了。为了找到它可爱的壳,蜗牛决定去所有的树梢寻找。没有了壳的保护,爬树是一件很危险的事情,因此它希望以最佳的方式搜寻这棵树。

幸运的是,树上生活着许多热心的蠕虫,这些蠕虫们能精确地告诉蜗牛,在它摔下之前是否曾经经过它们的地盘。

现在我们的任务是帮助这只蜗牛。我们把关注的重点放在树的两个部分——树枝的分叉和树枝的终点(即树梢)上,我们把这两者叫做结点,因为关键的事情总是在这里发生,比如选择一条路,从蠕虫那里得到帮助,或者抵达它所寻找的壳。

假定所有的蠕虫都生活在结点上,并且相邻结点之间树枝的长度为1.蜗牛现在在树的第一个分叉上。

我们的目标是:通过分析树的结构和蠕虫的位置,来找到一条适当的路径,使得蜗牛沿着这条路径能够尽快找到它的壳。对这条路径唯一的限制是:对于一个分叉,它必须在探查这个分叉所有的子结点之后才能从这个分叉上下来。当然,向蠕虫问路之后不再探查其子结点也是被允许的。

如图1所示,蜗牛正在节点1,并且它的壳在结点2,4,5之一。结点3有一只蠕虫,它可以告诉蜗牛,壳是否在结点4,5之一。因此,蜗牛可以选择两种策略。它可以先去结点2.如果它无法在这里找到壳,它应该返回节点1,然后通过节点3到达节点4(或5).如果仍然没有找到壳,它必须返回节点3,并且去节点5(或4),在那里它必然能够找到壳。在这种情况下,当壳在2,4(或5),5(或4)时,它爬过的长度相应为1,4,6。因此长度的期望值是(1+4+6)/3=11/3.显然,这种策略没有充分利用蠕虫提供的信息。如果蜗牛先去结点3,并且从蠕虫那里得到有用的信息,然后选择返回节点1后去节点2,或者去节点4,5之一尝试,那么在三种情况下,它爬过的长度将分别为2,3,4.在这种策略下,长度的期望值就是(2+3+4)/3=3,并且这就是蜗牛搜索整棵树的最好路线。


【输入格式】

输入文件的第一行有一个不超过1000的正整数N,代表结点的数量。

接下来的N行描述了N个结点。为了方便,我们将它们命名为1~N。1号结点总是树的第一个分叉。其他编号的结点可能是除此之外的任意结点。

这N行中的第i行描述了i号结点。每一行都由一个正整数和一个大写字母‘Y’或‘N’组成,它们分别代表这个结点的父结点和这个结点是否有蠕虫(Y是有,N是没有)。父结点的意思是,在这个结点和1号结点之间的最短路径上,和这个结点相邻的结点。在上面的图中,2号和3号结点的父结点是1号结点,同时4号和5号结点的父结点是3号结点。规定1号结点的父结点是-1,因为它没有父结点。假设一个分叉最多包含8条树枝。

第一组数据描述了上图。

【输出格式】

输出一行,一个实数,即整条路径最小的期望长度,保留4位小数。

【样例输入】

sample 1:


5

-1 N

1 N

1 Y

3 N

3 N


sample 2:



10

-1 N

1 Y

1 N

2 N

2 N

2 N

3 N

3 Y

8 N

8 N


sample 3:


6

-1 N

1 N

1 Y

1 N

3 N

3 N


【样例输出】

sample 1:


3.0000

sample 2:

5.0000

sample 3:

3.5000


【提示】

壳在每个树梢(即输入数据中树的叶子节点)的概率均等。

【来源】

2004年ACM,北京赛区

POJ2057 The Lost House