本文共 2416 字，大约阅读时间需要 8 分钟。
为了求解蜗牛从树根爬行到房子的最短期望距离，我们需要计算每个节点的最短爬行距离 die[i] 和成功爬行距离 win[i]。以下是详细的分析和解决方案：
定义：
die[i]：以节点 i 为根节点，无法找到房子时的最短爬行距离。win[i]：以节点 i 为根节点，找到房子时的最短爬行距离。节点属性：
pos[i]：节点 i 是否有毛毛虫（Y）。vec[i]：节点 i 的子节点列表。爬行规则：
递归计算：
die[i] 和 win[i]。计算方法：
die[i]：从节点 i 出发，无法找到房子的最短路径。 i 没毛毛虫，die[i] = die[j] + 1，j 为 i 的子节点。i 有毛毛虫，die[i] 为所有子节点的 die[j] + 1 中的最小值。win[i]：从节点 i 出发，找到房子的最短路径。 i 没毛毛虫，win[i] = die[j] + 1，j 为 i 的子节点。i 有毛毛虫，win[i] 为所有子节点的 win[j] 中的最小值。优化访问顺序：
cmp(a, b)，优先处理更可能成功的子节点，减少重复路径。#include#include #include using namespace std;const int maxn = 1010;int pos[maxn];int snode[maxn];int die[maxn];int win[maxn];int n;vector > vec;void init() { memset(pos, 0, sizeof(pos)); memset(snode, 0, sizeof(snode)); memset(die, 0, sizeof(die)); memset(win, 0, sizeof(win)); char ps; int pre; for (int i = 1; i <= n; ++i) { vec[i].clear(); } for (int i = 1; i <= n; ++i) { scanf("%d %c%*c", &pre, &ps); if (pre == -1) continue; vec[pre].push_back(i); pos[i] = (ps == 'Y') ? 1 : 0; }}int cmp(int a, int b) { return (die[a] + 2) * snode[b] < (die[b] + 2) * snode[a];}void dfs(int x) { int len = vec[x].size(); for (int i = 0; i < len; ++i) { int j = vec[x][i]; if (!cmp(j, i)) continue; if (pos[j] == 0) { die[j] = die[x] + 1; win[j] = die[j]; } else { die[j] = die[x] + 1; if (pos[j]) { win[j] = win[j] ? min(win[j], win[x] + 1) : win[x] + 1; } else { win[j] = die[j]; } } dfs(j); if (pos[j]) { if (win[j] < win[x]) { win[x] = win[j]; } } else { if (die[j] + 1 < die[x]) { die[x] = die[j] + 1; } } }}void main() { init(); for (int i = 1; i <= n; ++i) { if (!snode[i]) continue; dfs(i); }}
初始化：
init() 函数初始化所有数组和向量，读取输入数据并构建树结构。比较函数：
cmp(a, b) 根据 die 和 snode 值确定访问顺序，优先处理更可能成功的分支。递归DFS：
dfs(x) 处理节点 x，计算 die[x] 和 win[x]。j，根据 pos[j] 判断是否有毛毛虫，更新 die 和 win。j，更新当前节点的 win 和 die。主函数：
dfs 计算最短距离。通过以上方法，我们可以高效地计算蜗牛从树根爬行到房子的最短期望距离，确保在处理毛毛虫的询问顺序时，减少重复路径，优化整体性能。
转载地址：http://guxfk.baihongyu.com/