Solution

核心思路

定义 $dp[i][j]$ 为妖怪 $i$ 和 $j$ 基因相同的概率。利用记忆化搜索求解：

1. ‌边界‌：若 $i=j$，概率为 $1$；若两人均为始祖且 $i \neq j$，概率为 $0$。
2. ‌转移‌：
   • 若仅 $i$ 有父母 $fa, mo$：$dp[i][j] = 0.5 \cdot dp[fa][j] + 0.5 \cdot dp[mo][j]$
   • 若均有父母：$dp[i][j] = 0.25 \sum dp[fa_i][fa_j...]$