OI题库

【题目描述】

一天，一只蜗牛爬到了一棵大树上，它爬呀爬，最终爬到了树梢。它从来没有从这么高的地方向下看过，这真是一种新奇的感受！但由于爬了这么长时间，它已经很累了，很快便睡着了。当它醒来的时候，发现发生了一件不可思议的事情——它发现自己躺在一片草地上，并且自己原来背着的壳（英文原题中为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