P13350 「ZYZ 2025」遗传

唉，转生竞吧！

**如果你不了解生物的遗传学知识，可以阅读以下部分：** > 每个生物 M 都有两个属性，记属性一为 $X\in\{A,a\}$，属性二为 $Y\in\{A,a\}$，称 $XY$ 为其**基因型**，包括 $AA,Aa,aa$ 三种，这里认为 $Aa$ 和 $aA$ 等价。 > > 对于生物 M 可患的遗传病 I，若 I 为**隐性遗传病**，则该生物患病当且仅当其基因型为 $aa$，若 I 为**显性遗传病**，则该生物患病当且仅当其基因型为 $Aa$ 或 $AA$。 > > 若基因型为 $X_1Y_1$ 和 $X_2Y_2$ 的生物交配，则其后代的基因型有四种情况：$X_1X_2,X_1Y_2,Y_1X_2,Y_1Y_2$，且每种情况的概率相同，均为 $\dfrac{1}{4}$。 > > 若 $A$ 的**基因频率**为 $p$，则认为在没有其他条件的影响下（在本题中“其他条件”包括“知道其父母”），一个生物 M 的两个属性各自有 $p$ 的概率为 $A$，$1-p$ 的概率为 $a$，且相互独立。 > > 现在有一种生物 M 可患的遗传病 I，已知其是显性还是隐性，$A$ 的基因频率为 $p$。 **否则，你可以阅读以下部分：** > 现在有一种和生物 M 有关的遗传病 I，已知其是显性还是隐性，其受一对常染色体等位基因 $(A,a)$ 控制，该基因的遗传符合孟德尔遗传规律，不考虑基因突变、染色体变异，交叉互换等特殊情况。 > > **已知** $A$ 的基因频率是 $p$，即认为在没有其他条件的影响下（在本题中“其他条件”包括“知道其父母”），一个生物 M 的两个基因各自有 $p$ 的概率为 $A$，$1-p$ 的概率为 $a$，且相互独立。 现在有 $n$ 个生物 M，第 $i$ 个生物的父亲为 $fa_i$，母亲为 $mo_i$，若 $fa_i=0$ 或 $mo_i=0$ 则表示父亲或母亲未知。为了简化问题，保证 $fa_i$ 和 $mo_i$ 要么**均为** $0$，要么**均不为** $0$，且**恰有一个**生物 M 没有孩子，其余生物 M **恰有一个孩子**。 给出 $n$ 个生物的关系，已知部分生物的患病情况，你需要分别求出每一个生物基因型为 $AA,Aa,aa$ 的概率，对 $10^9+7$ 取模。 你可以参见样例解释以更好的理解这个题目。 **保证数据合法且保证数据随机生成**。

第一行输入四个整数 $n,t,a,b$，$n$ 表示生物总数，$t = 0$ 表示疾病 I 为隐性，$t = 1$ 表示疾病 I 为显性，$A$ 的基因频率 $p=\dfrac{a}{b}$。 接下来 $n$ 行，第 $i$ 行首先输入一个整数 $k_i$，若 $k_i=0$ 表示第 $i$ 个生物患病，$k_i=1$ 表示不患病，$k_i=2$ 表示患病状况未知。再输入两个整数 $fa_i,mo_i$ 分别表示其父亲、母亲的编号，若编号为 $0$，则表示父母未知。

输出 $n$ 行，其中的第 $i$ 行输出三个整数，分别表示第 $i$ 个生物基因型为 $AA,Aa,aa$ 的概率，结果对 $10^9+7$ 取模。

**【样例解释】** 记第 $i$ 个生物为 $M_i$，其基因型为 $S_i$。由于 $M_2$ 患隐性遗传病，所以 $S_2=aa$ 且 $M_3$ 含有基因（属性）$a$。又因为 $M_3$ 不患病，所以 $S_3=Aa$。 因为 $M_1$ 和患病的 $M_2$ 生出不患病的 $M_3$，所以 $M_1$ 一定不患病。因为 $p=\dfrac12$，所以对于一个随机的不患病的个体，其基因型为 $AA$ 和 $Aa$ 的概率之比为： $$\left(\dfrac12\times\dfrac12\right):\left(2\times\dfrac12\times(1-\dfrac12)\right)=1:2$$ 又因为基因型为 $AA$ 和 $aa$ 的个体生出 $Aa$ 个体的概率为 $1$，基因型为 $Aa$ 和 $aa$ 的个体生出 $Aa$ 个体的概率为 $\dfrac12$，所以 $S_1$ 为 $AA$ 和 $Aa$ 的概率之比为： $$\left(\dfrac13\times1\right):\left(\dfrac23\times\dfrac12\right)=1:1$$ 所以 $S_1$ 为 $AA$ 和 $Aa$ 的概率相同，均为 $\dfrac12$。 **【数据范围】** **本题采用捆绑测试。** |子任务编号|特殊性质|分值| |:-:|:-:|:-:| |$0$|$n\leq5$|$15$| |$1$|任意 $i\in[1,n]$ 满足 $k_i=2$|$15$| |$2$|$n\leq 5\times 10^3$|$30$| |$3$|无|$40$| 对于 $100\%$ 的测试数据，保证：$1\leq fa_i,mo_i\leq n \leq10^5$，$t\in\{0,1\}$，$1\leq a< b\leq 10^9$，$k_i\in\{0,1,2\}$，保证出现题目给出情况的概率在模 $10^9+7$ 意义下不为 $0$，**保证数据随机生成**。