问题背景与分析

题目描述了一个蜗牛在树上寻找自己房子的问题。树的结构由关键点和树枝组成，关键点包括分叉点和树枝的尽头。蜗牛的目标是以最小的期望距离找到自己的房子。为了实现这一目标，蜗牛需要利用虫子提供的信息来优化搜索路径。

关键点在于：

1. 树的结构：树是一个有向无环图，关键点之间通过树枝相连。
2. 虫子的作用：虫子可以告诉蜗牛某个子树中是否包含房子，从而帮助蜗牛避免不必要的搜索。
3. 期望距离：我们需要计算蜗牛找到房子的期望距离，即所有可能路径的平均距离。

算法思路

1. 树的构建：

   • 使用邻接表G表示树的结构，G[i]存储以关键点i为父节点的所有子节点。
   • worm[i]表示关键点i是否有虫子（1表示有，0表示没有）。

2. 深度优先搜索（DFS）：

   • 从根节点（关键点1）开始，递归地遍历整棵树。
   • 对于每个节点，计算以下三个值：
     • son[i]：以节点i为根的子树中叶子节点的数量。
     • suc[i]：从节点i开始，找到房子的总成功路径长度。
     • fail[i]：从节点i开始，未找到房子的总失败路径长度。

3. 子节点排序：

   • 在处理每个节点时，先对子节点按照cmp函数进行排序。cmp函数的目的是优先选择失败代价较小的子节点，从而优化搜索路径。

4. 期望距离的计算：

   • 对于每个节点，根据子节点的son、suc和fail值，计算当前节点的son、suc和fail值。
   • 最终，根节点的期望距离为suc[0] / son[0]。

代码实现

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define abs(x) ((x) < 0 ? -(x) : (x))
#define INF 0x3f3f3f3f
#define delta 0.85
using namespace std;

#define maxn 1005
int N;
int worm[maxn];
int suc[maxn], fail[maxn], son[maxn];
vector<int> G[maxn];

// 比较函数，优先选择失败代价较小的子节点
bool cmp(int a, int b)
{
	return (fail[a] + 2) * son[b] < (fail[b] + 2) * son[a];
}

// 深度优先搜索
void dfs(int p)
{
	int n = G[p].size();
	if (n == 0) // 如果是叶子节点
	{
		son[p] = 1, suc[p] = fail[p] = 0; // 叶子节点的子树只有一个节点，成功路径长度为0，失败路径长度为0
		return;
	}
	vector<int> &ch = G[p];
	for (int i = 0; i < n; i++) // 递归处理所有子节点
	{
		dfs(ch[i]);
	}
	sort(ch.begin(), ch.end(), cmp); // 按照cmp函数对子节点排序
	int fsum = 0; // 用于记录失败路径的累积长度
	for (int i = 0; i < n; i++) // 遍历所有子节点
	{
		int u = ch[i];
		if (worm[p]) // 如果当前节点有虫子
		{
			fail[p] = 0; // 失败路径长度为0
		}
		else
		{
			fail[p] += fail[u] + 2; // 失败路径长度加上子节点的失败路径长度和额外的2（来回距离）
		}
		son[p] += son[u]; // 当前节点的子树叶子节点数量加上子节点的子树叶子节点数量
		suc[p] += suc[u] + son[u] * (1 + fsum); // 当前节点的成功路径长度加上子节点的成功路径长度和额外的距离
		fsum += fail[u] + 2; // 更新失败路径的累积长度
	}
}

// 解决问题
void solve()
{
	memset(suc, 0, sizeof(suc)); // 初始化成功路径长度数组
	memset(fail, 0, sizeof(fail)); // 初始化失败路径长度数组
	memset(son, 0, sizeof(son)); // 初始化子树叶子节点数量数组
	dfs(0); // 从根节点开始进行深度优先搜索
	printf("%.4lf\n", (double)suc[0] / son[0]); // 输出期望距离
}

int main()
{
	while (~scanf("%d", &N) && N) // 处理多组测试数据
	{
		for (int i = 0; i < N; i++) // 清空邻接表
		{
			G[i].clear();
		}
		for (int i = 0; i < N; i++) // 读取输入并构建树
		{
			int u;
			char c;
			scanf("%d %c", &u, &c);
			worm[i] = (c == 'Y' ? 1 : 0); // 标记是否有虫子
			if (i > 0) // 如果不是根节点
			{
				G[u - 1].push_back(i); // 将当前节点加入其父节点的子节点列表
			}
		}
		solve(); // 调用solve函数解决问题
	}
	return 0;
}

样例解释

以样例输入中的第一组为例：

5
-1 N
1 N
1 Y
3 N
3 N

• 树的结构：
  • 关键点1是根节点，有两个子节点2和3。
  • 关键点3有两个子节点4和5。
• 搜索过程：
  • 蜗牛从关键点1开始，先访问关键点3（因为关键点3有虫子，可以提供信息）。
  • 如果关键点3的虫子确认房子在4或5中，蜗牛会优先选择距离较短的路径。
  • 如果关键点3的虫子确认房子不在4和5中，蜗牛会返回关键点1，然后前往关键点2。
• 期望距离计算：
  • 如果房子在关键点2，距离为1。
  • 如果房子在关键点4或5，距离分别为3和4。
  • 期望距离为(1 + 3 + 4) / 3 = 3.0000。

总结

本题的核心是利用深度优先搜索和贪心策略（通过cmp函数优化子节点的访问顺序），计算出蜗牛找到房子的最小期望距离。通过合理利用虫子提供的信息，可以显著减少不必要的搜索路径，从而降低期望距离。