官方题解只能做到 $O(n^2)$？玩的太差了。这题可以严格突破已有题解的 $O(n^2)$，下面给出一个完整实现的次二次算法。设矩阵乘法的复杂度为 $O(k^\omega)$，则算法的时间复杂度为 $\widetilde O(n^{3-4/(\omega+1)})$，其中 $\widetilde O$ 隐去了对数因子。
这是一个已证明并实现的上界；没有匹配的下界，因此不声称它已经最优。
从抽卡转化为多项式积分
记 $p_{u,j}=a_{u,j}/(a_{u,1}+a_{u,2}+a_{u,3})$。题目中的约束共有 $n-1$ 条，忽略方向后连通，因此它们构成一棵树。我们要求所有有向边 $u\to v$ 都满足 $T_u< T_v$ 的概率。([UOJ][2])
先固定所有权值。忽略重复抽到的卡片后，下一张新卡是 $u$ 的概率，等于 $W_u$ 除以尚未出现的卡片的权值总和。这也恰好是相互独立的指数随机变量 $E_u\sim\operatorname{Exp}(W_u)$ 从小到大排列的分布：最小者按速率比例产生，去掉最小者后，由无记忆性得到同样的过程。
令 $X_u=e^{-E_u}$。条件 $T_u< T_v$ 就变成 $X_u>X_v$；当 $W_u=j$ 时，$X_u$ 在 $(0,1)$ 上的密度为 $jx^{j-1}$。对权值取平均，得到二次多项式密度 $q_u(x)=p_{u,1}+2p_{u,2}x+3p_{u,3}x^2$。
任意选根。定义 $G_u(x)$ 表示父亲的变量取值为 $x$ 时，$u$ 的子树以及父子边都满足约束的概率。
令 $F_u(x)=q_u(x)\prod_{v\text{ 是 }u\text{ 的儿子}}G_v(x)$。若边为父亲 $\to u$，则要求 $X_u< x$，所以 $G_u(x)=\int_0^x F_u(t),dt$；若边为 $u\to$ 父亲，则 $G_u(x)=\int_x^1F_u(t),dt$。根使用第一种定义，最终答案为 $G_{\mathrm{root}}(1)$。
所有消息都是多项式，并且 $\deg G_u\le 3\operatorname{sz}_u$。按系数直接维护，就是平方复杂度的算法。
真正的瓶颈出现在长链上：即使每次只乘一个二次多项式，也要扫描整个已有多项式完成积分，总工作量仍然可以达到 $\Theta(n^2)$。因此，必须把连续多个“乘多项式、积分”的操作一起处理。
把一段重链合并成一个算子
按子树大小做重链剖分。设 $h(u)$ 是重儿子，把所有轻儿子的贡献提前乘起来，记 $P_u(x)=q_u(x)\prod_{v\ne h(u)}G_v(x)$。
沿一条重链自底向上，剩下的操作就只有 $f\mapsto\int_0^xP_u(t)f(t),dt$ 和 $f\mapsto\int_x^1P_u(t)f(t),dt$。定义这一步的“次数增量”为 $d_u=\deg P_u+1$，则 $d_u\le 3(1+\sum_{v\text{ 是轻儿子}}\operatorname{sz}_v)$，从而 $\sum_u d_u=O(n\log n)$。
考虑一段次数增量总和为 $D$ 的操作。它们的复合一定可以写成
$$ T[f](x)=\int_0^x U(x,y)f(y)\,dy+\int_0^1 V(x,y)f(y)\,dy, $$
其中 $U,V$ 都是总次数小于 $D$ 的二元多项式。
单次下限积分对应 $U(x,y)=P(y),V=0$；单次上限积分对应 $U(x,y)=-P(y),V(x,y)=P(y)$。继续复合时交换积分顺序，内层仍然是多项式积分，因此这个表示保持成立，而且每次总次数恰好多增加至多 $\deg P+1$。
第二项不能省略。 它保存了所有反向边产生的边界贡献；只处理第一项，会把本题错误地变成所有边方向相同的版本。
下面分别解决算子的构造和应用。
如何在 $\widetilde O(D^\omega)$ 时间内构造算子。
以 $1,x,x^2,\ldots$ 为基，令 $M_{i,k}=[x^i]T[x^k]$。算子的复合就是矩阵乘法，因此可以分治合并一段操作。
关键在于：需要在二元核 $(U,V)$ 和一个 $O(D)$ 阶的矩阵之间快速转换，否则仍然会出现立方瓶颈。
第一项只会提高次数。把提高的次数记为 $d$，定义 $S_d(k)=\sum_{b=0}^{d-1}U_{d-1-b,b}/(k+b+1)$，那么它对矩阵的贡献就是 $M_{k+d,k}\mathrel{+}=S_d(k)$。第二项对第 $i$ 行的贡献为 $\sum_bV_{i,b}/(k+b+1)$。
这些式子都是形如 $\sum_jc_j/(j+k+1)$ 的 Cauchy 矩阵乘向量。把 $c$ 倒序后，与逆元序列卷积，即可一次算出所有 $k$ 的结果。因此，从核构造矩阵只需要 $\widetilde O(D^2)$。
反过来，设 $R_d(z)=(z+1)\cdots(z+d)S_d(z)$。分母被消去后，$R_d$ 是次数小于 $d$ 的多项式。
取 $k=D-d,\ldots,D-1$，此时输出次数 $k+d\ge D$，不会受到 $V$ 的影响，所以能直接读出 $R_d(k)=M_{k+d,k}(k+d)!/k!$。由这 $d$ 个连续点的值，通过连续点插值求出 $R_d(-1),\ldots,R_d(-d)$，再利用 $R_d(-b-1)=(-1)^b b!(d-1-b)!,U_{d-1-b,b}$，恢复 $U$。
减去 $U$ 的贡献后，矩阵左上角的 $D\times D$ 部分满足 $W=VH$，其中 $H_{i,j}=1/(i+j+1)$。这个 Hilbert 矩阵的逆具有显式形式 $H^{-1}=\operatorname{diag}(c)H\operatorname{diag}(c)$，其中 $c_i=(-1)^i(D+i)!/((D-i-1)!(i!)^2)$。所以恢复 $V$ 仍然只需要逐行做 Cauchy 卷积，总时间为 $\widetilde O(D^2)$。
合并次数增量分别为 $D_1,D_2$ 的两个算子时，令 $D=D_1+D_2$，使用至少 $2D$ 阶的矩阵。我们只需要复合结果的前 $D$ 列；这些输入经过第一个算子后，次数小于 $2D$，因此截断不会丢掉随后可能通过边界项回到低次的贡献。这个截断条件也不能省略。
于是，分治构造整个核的时间为 $\widetilde O(D^\omega)$。
如何快速把算子作用到一个长多项式上。
设输入有 $m$ 个系数。对于 $V$ 部分，先通过一次卷积求出 $h_b=\int_0^1y^bf(y),dy=\sum_k f_k/(k+b+1)$，再计算 $\sum_bV_{a,b}h_b$，时间为 $\widetilde O(m+D^2)$。
困难的是 $U$ 部分。做阶乘换基 $\mathcal B(\sum_kf_kx^k)=\sum_k k!f_kx^k$，并令 $\theta=x\frac d{dx}$，于是 $\theta x^k=kx^k$。
在这个基下，$U$ 对应的算子恰好为 $L=\sum_{d=1}^D x^dR_d(\theta)$：作用于 $x^k$ 时，系数乘上 $R_d(k)$，次数提高 $d$。
这里使用“换基、小步大步、矩阵乘法”来批量求值；类似的组织方式也用于快速微分算子求值。下面的边界核恢复和树上分块则需要另外处理。([arXiv][3])
由交换关系 $\theta x^d=x^d(\theta+d)$，可以先把所有 $\theta$ 移到左侧，得到 $L=\sum_dA_d(\theta)x^d$，其中 $A_d(z)=R_d(z-d)$。这些多项式在连续点上的值可以直接从核读出：$A_d(a)=(-1)^{d-1-a}a!(d-1-a)!,U_{a,d-1-a}$，其中 $0\le a< d$。
取 $K$ 为不小于 $\sqrt D$ 的最小二次幂。把 $A_d$ 的次数按每 $K$ 项分组，再利用交换关系把每组内部的低次幂移回右侧，即可得到 $L=\sum_{q< K}\theta^{qK}\sum_{r< K}B_{q,r}(x)\theta^r$，其中每个 $B_{q,r}$ 的次数至多为 $D$。插值和多项式平移合计需要 $\widetilde O(D^2)$。
令 $F=\mathcal B(f)$。先生成小步多项式 $F,\theta F,\ldots,\theta^{K-1}F$，然后按每 $D+1$ 个系数切块。计算 $\sum_rB_{q,r}(x)\theta^rF$，就变成一个 $K\times K$ 的多项式矩阵，乘一个 $K\times s$ 的多项式矩阵，其中 $s=O(1+m/D)$。
每次处理 $K$ 列。对矩阵中的多项式做 NTT，在每个频点使用 Strassen 乘法，最后逆变换。每组代价为 $\widetilde O(DK^\omega)$，一共 $O(1+m/(DK))$ 组。
得到结果后，巨步 $\theta^{qK}$ 只需把次数为 $k$ 的系数乘上 $k^{qK}$。注意这里使用的是全局次数，不是系数块内的下标。
因此，一次应用的复杂度为 $\widetilde O(D^{1+\omega/2}+mD^{(\omega-1)/2})$。加上构造核的代价，并利用 $1+\omega/2\le\omega$，一个块的总复杂度为 $\widetilde O(D^\omega+mD^{(\omega-1)/2})$。
复杂度与 C++17 实现
用阈值 $B$ 划分每条重链，普通块的次数增量之和不超过 $B$。单个 $d_u>B$ 的操作单独处理；每条链最后剩下的一小段直接递推。
除去每条链最后的短段，块数为 $O(n\log n/B)$：相邻普通块可以按总重量至少 $B$ 配对计数，而大操作及它前面的短块可以直接向 $d_u>B$ 收费。
所有核的构造代价为 $\widetilde O(nB^{\omega-1})$。每次应用时 $m=O(n)$，所以所有应用的总代价为 $\widetilde O(n^2/B^{(3-\omega)/2})$。
大操作的代价为 $\widetilde O(n^2/B)$。每条链最后的短段至多包含 $B$ 步，而所有重链链头的子树大小之和为 $O(n\log n)$，因此短段总代价为 $\widetilde O(nB)$。这两部分都被前面的界覆盖。轻儿子的多项式乘积按大小合并，总代价为 $\widetilde O(n)$。
取 $B=\lceil n^{2/(\omega+1)}\rceil$，得到
$$ \widetilde O\!\left(nB^{\omega-1}+\frac{n^2}{B^{(3-\omega)/2}}\right) =\widetilde O\!\left(n^{3-\frac4{\omega+1}}\right). $$
处理多项式矩阵时逐组生成输入，不存储全部小步多项式，空间为 $O(n+B^2)$。
提交记录：https://qoj.ac/submission/2939119 。 CTS 的题就是简单。