可以。下面给你整理成一份比较像正式题解/论文式说明的版本，目标是从原题的 $O(n^2)$ DP 出发，完整推到 $O(M(n)\log n)$。我会把两个最关键的地方展开：
- 为什么二维 DP 可以变成“祖先链多项式取商后求值”；
- 为什么再用全局平衡的 rake/compress（可理解为静态 Top Tree）后，可以做到 $O(M(n)\log n)$，而不是多一个 $\log$。
原题官方题解的算法七已经给出了一个 $O(n^2)$ 的统一 DP：通过染色过程，将拓扑序与染色方案对应起来，然后维护“当前首个未染黑祖先”为 $u$ 的方案数。
题解：树上拓扑序位置权值和的 $O(M(n)\log n)$ 算法
1. 问题
给定一棵以 $1$ 为根的有根树。
一个排列 $a_1,\dots,a_n$ 是合法拓扑序，当且仅当每个点都出现在其父亲之后，即父亲一定比儿子更早出现。
另给定权值
$$ b_1,b_2,\dots,b_n. $$
对每个点 $u$，要求
$$ f(u)= \sum_{\text{合法拓扑序 }a} b_{\operatorname{pos}_a(u)}. $$
原题的定义与输入输出见题面。
以下所有运算都在
$$ \mathbb F_p,\qquad p=10^9+7 $$
中进行。
记 $s_u$ 为 $u$ 的子树大小。
我们记多项式乘法 $m$ 次的复杂度为 $M(m)$，并假设通常的正规条件
$$ M(2m)=O(M(m)),\qquad \frac{M(m)}m \text{ 单调不减}. $$
最终复杂度为
$$ \boxed{O(M(n)\log n)}. $$
若用 FFT/NTT 意义下的
$$ M(n)=O(n\log n), $$
则得到
$$ O(n\log^2n). $$
2. 从官方算法七开始
官方题解的算法七考虑这样一个染色过程：
一开始全部点是白色。
每轮任选一个白点，然后把它祖先中深度最浅的白点染黑。
最终染黑次序一定构成一个合法拓扑序，而且任意一个拓扑序恰好对应
$$ \prod_{u=1}^n s_u $$
种染色方式。
记
$$ H=\prod_{u=1}^n s_u. $$
因此，我们可以先计算在所有染色方案中，点 $u$ 第 $i+1$ 个被染黑的方案数，再除以 $H$。
2.1 官方 DP
定义
$$ D_{i,u} $$
表示经过 $i$ 轮染色以后，当前从根往下第一个还没被染黑的点是 $u$ 的方案数。
初值为
$$ D_{0,u}=[u=1]. $$
对于 $i\ge1$，有
$$ D_{i,u} = (n-i+1-s_u)D_{i-1,u} +s_{\operatorname{fa}_u}D_{i-1,\operatorname{fa}_u}, $$
根没有第二项。
这是官方算法七最后得到的统一转移。
若第 $i+1$ 轮染黑的是 $u$，则这一轮选择的白点必须在 $u$ 子树里，因此有 $s_u$ 种选择；后面剩下的选择可以任意排列。
故第 $i+1$ 个位置为 $u$ 的染色方案数为
$$ s_u (n-1-i)!\,D_{i,u}. $$
于是
$$ f(u) = \frac{s_u}{H} \sum_{i=0}^{n-1} b_{i+1}(n-1-i)!\,D_{i,u}. \tag{1} $$
直接计算所有 $D_{i,u}$ 是 $O(n^2)$。
接下来最重要的是把这张二维表消掉。
3. 第一个关键转化：归一化 DP
定义
$$ \lambda_u=n-s_u. $$
再定义
$$ t_u= \prod_{\substack{v\text{ 是 }u\text{ 的严格祖先}}}s_v. $$
特别地，
$$ t_1=1, \qquad t_u=t_{\operatorname{fa}_u}s_{\operatorname{fa}_u}. $$
令
$$ E_{i,u}=\frac{D_{i,u}}{t_u}. $$
代入 DP：
$$ \begin{aligned} E_{i,u} &= (n-i+1-s_u)E_{i-1,u} + \frac{ s_{\operatorname{fa}_u} D_{i-1,\operatorname{fa}_u}} {t_u}\\ &= (\lambda_u-i+1)E_{i-1,u} + E_{i-1,\operatorname{fa}_u}. \end{aligned} $$
所以得到极其整齐的转移
$$ \boxed{ E_{i,u} = (\lambda_u-i+1)E_{i-1,u} + E_{i-1,\operatorname{fa}_u}. } \tag{2} $$
边界仍然是
$$ E_{0,u}=[u=1]. \tag{3} $$
现在问题就变成：如何同时计算
$$ \sum_i c_iE_{i,u}, \qquad c_i=b_{i+1}(n-1-i)!. $$
4. 第二个关键转化：把 DP 变成多项式取商
这是整个算法最核心的恒等式。
定义下降阶乘
$$ x^{\underline i} = x(x-1)\cdots(x-i+1), \qquad x^{\underline0}=1. $$
对每个点 $u$，定义
$$ A_u(x) = \prod_{\substack{v\text{ 是 }u\text{ 的严格祖先}}} (x-\lambda_v). $$
于是根有
$$ A_1(x)=1. $$
定义一个线性泛函
$$ \boxed{ L_u(F) = \left(F\operatorname{quo}A_u\right)(\lambda_u), } \tag{4} $$
其中 $F\operatorname{quo}G$ 表示普通多项式带余除法中的商。
关键结论是
$$ \boxed{ L_u(xF) = \lambda_uL_u(F) + L_{\operatorname{fa}_u}(F) } \tag{5} $$
对于根，第二项视为 $0$。
4.1 证明恒等式 (5)
设 $p=\operatorname{fa}_u$。
因为
$$ A_u=A_p(x-\lambda_p). $$
将 $F$ 除以 $A_u$：
$$ F=A_uQ+R, \qquad \deg R<\deg A_u. $$
于是
$$ xF=A_u(xQ)+xR. $$
所以
$$ (xF)\operatorname{quo}A_u = xQ+(xR)\operatorname{quo}A_u. $$
由于
$$ \deg R<\deg A_u, $$
所以 $xR$ 的次数至多等于 $\deg A_u$。
因此
$$ (xR)\operatorname{quo}A_u $$
只是一个常数，而且因为 $A_u$ 是首一多项式，这个常数恰好等于 $R$ 的最高次项系数。
另一方面，
$$ F\operatorname{quo}A_p = (x-\lambda_p)Q+(R\operatorname{quo}A_p). $$
代入 $x=\lambda_p$，第一项消失：
$$ L_p(F) = (R\operatorname{quo}A_p)(\lambda_p). $$
注意
$$ \deg R<\deg A_p+1, $$
故
$$ R\operatorname{quo}A_p $$
同样只是常数，而且恰好也是 $R$ 的最高次项系数。
因此
$$ (xR)\operatorname{quo}A_u = L_p(F). $$
所以
$$ \begin{aligned} L_u(xF) &= \lambda_uQ(\lambda_u)+L_p(F)\\ &= \lambda_uL_u(F)+L_p(F). \end{aligned} $$
恒等式得证。
5. DP 恰好就是下降阶乘在这些泛函下的值
注意
$$ x^{\underline i} = (x-i+1)x^{\underline{i-1}}. $$
利用 (5)，
$$ \begin{aligned} L_u(x^{\underline i}) &= L_u\bigl((x-i+1)x^{\underline{i-1}}\bigr)\\ &= (\lambda_u-i+1) L_u(x^{\underline{i-1}}) + L_{\operatorname{fa}_u}(x^{\underline{i-1}}). \end{aligned} $$
这正好和 (2) 完全一致。
同时
$$ L_u(1) = (1\operatorname{quo}A_u)(\lambda_u) = [u=1], $$
也和 (3) 一致。
因此由递推唯一性，
$$ \boxed{ E_{i,u}=L_u(x^{\underline i}). } \tag{6} $$
这就是二维 DP 被多项式语言完全吸收掉的地方。
6. 把所有位置权值一次性塞进一个多项式
定义
$$ c_i=b_{i+1}(n-1-i)!. $$
构造
$$ \boxed{ P(x) = \sum_{i=0}^{n-1} c_i x^{\underline i}. } \tag{7} $$
由线性性和 (6)，
$$ \begin{aligned} L_u(P) &= \sum_i c_i L_u(x^{\underline i})\\ &= \sum_i b_{i+1}(n-1-i)!E_{i,u}. \end{aligned} $$
设
$$ h_u=L_u(P). $$
则根据
$$ D_{i,u}=t_uE_{i,u} $$
以及公式 (1)，最终答案为
$$ \boxed{ f(u)= \frac{s_ut_u}{H}\,h_u. } \tag{8} $$
所以整个原问题已经被转化成：
给定一棵树，每个点有参数 $\lambda_u$，以及一个次数 $<n$ 的多项式 $P$，求所有
$$ \boxed{ h_u= \left( P\operatorname{quo} \prod_{v\text{ 是 }u\text{ 的严格祖先}} (x-\lambda_v) \right)(\lambda_u). } \tag{9} $$
到这里以后，原来的组合意义基本已经不需要了。
7. 把“取商后求值”改写成有理函数系数
定义
$$ G_u(x) = \prod_{v\in\operatorname{path}(1,u)} (x-\lambda_v) = A_u(x)(x-\lambda_u). $$
我们有
$$ \boxed{ h_u = [x^{-1}] \frac{P(x)}{G_u(x)}. } \tag{10} $$
这里 $[x^{-1}]$ 表示在 $x=\infty$ 处展开成 Laurent 级数以后 $x^{-1}$ 的系数。
7.1 证明公式 (10)
将 $P$ 对 $A_u$ 做带余除法：
$$ P=A_uC+R, \qquad \deg R<\deg A_u. $$
于是
$$ \frac P{G_u} = \frac C{x-\lambda_u} + \frac R{A_u(x-\lambda_u)}. $$
由于
$$ \deg R<\deg A_u, $$
第二项在无穷远处是
$$ O(x^{-2}), $$
不会贡献 $x^{-1}$ 项。
而
$$ \frac{C(x)}{x-\lambda_u} $$
的 $x^{-1}$ 系数恰好为
$$ C(\lambda_u). $$
所以
$$ [x^{-1}]\frac P{G_u} = C(\lambda_u) = (P\operatorname{quo}A_u)(\lambda_u) = h_u. $$
证毕。
这一转化非常重要，因为它使得祖先链上的多项式除法变成了树上一类非常自然的有理函数 DP。
8. 引入辅助变量，得到树形有理函数 DP
给每个点引入一个形式变量 $z_u$。
定义
$$ \boxed{ R_u(x) = \frac{ z_u+\sum_{v\text{ 是 }u\text{ 的儿子}}R_v(x) } {x-\lambda_u}. } \tag{11} $$
展开以后显然有
$$ R_1(x) = \sum_{u=1}^n \frac{z_u}{G_u(x)}. \tag{12} $$
因此根据 (10)，
$$ \begin{aligned} [x^{-1}]P(x)R_1(x) &= \sum_u z_u [x^{-1}] \frac{P(x)}{G_u(x)}\\ &= \boxed{ \sum_u z_uh_u. } \end{aligned} $$
也就是说：
如果能够快速计算线性映射
$$ (z_1,\dots,z_n)\longmapsto R_1, $$
那么把这个计算过程转置，就可以一次求出所有 $h_u$。
问题变成构造这个线性电路。
9. 不约分，统一使用公分母
令
$$ Q(x) = \prod_{u=1}^n(x-\lambda_u). \tag{14} $$
我们始终不进行任何约分。
将
$$ R_1=\frac{N_z(x)}{Q(x)}, \qquad \deg N_z<n. $$
其中 $N_z$ 关于所有 $z_u$ 都是线性的。
于是
$$ \sum_u z_uh_u = [x^{-1}] \frac{P(x)N_z(x)}{Q(x)}. \tag{15} $$
因此真正要快速实现的是线性映射
$$ \boxed{ z\longmapsto N_z. } $$
10. 为什么普通树形 DP 还是会平方
当然可以对每个点维护
$$ R_u=\frac{B_u}{D_u}. $$
但如果直接按照原树向上合并，长链上会出现长度
$$ 1,2,3,\dots,n $$
的多项式，总代价仍然可能是二次的。
所以我们需要将整棵树重新组织成一棵全局高度 $O(\log n)$ 的二叉合并树。
这就是这里所谓的 Top Tree / 全局平衡 rake-compress。
它不需要支持动态 link/cut，只需要离线构造一棵静态的平衡合并树即可。
11. Heavy-Light 只是用来定义两种合并
对每个非叶点 $u$，任选一个子树最大的儿子作为重儿子
$$ h(u). $$
其余儿子称为轻儿子。
定义
$$ \boxed{ w_u=s_u-s_{h(u)}, } \tag{16} $$
叶子视作 $s_{h(u)}=0$。
于是
$$ w_u = 1+ \sum_{\substack{v\text{ 是 }u\text{ 的}\\\text{轻儿子}}} s_v. \tag{17} $$
也就是说，$w_u$ 正好是：
- 点 $u$ 自身；
- 所有挂在 $u$ 上的轻子树；
包含的总点数。
把这整个部分视为重链上的一个“原子”。
12. Rake：横向合并轻子树
假设两个互不相交的子树块分别表示有理函数
$$ \frac{B_1}{D_1}, \qquad \frac{B_2}{D_2}. $$
因为轻儿子之间只是做加法，所以
$$ \frac{B_1}{D_1} + \frac{B_2}{D_2} = \frac{ B_1D_2+B_2D_1 }{ D_1D_2 }. $$
因此 rake 合并公式为
$$ \boxed{ \begin{aligned} B&=B_1D_2+B_2D_1,\\ D&=D_1D_2. \end{aligned} } \tag{18} $$
一次合并只需要常数次多项式乘法。
注意我们完全不要求 $D_1,D_2$ 互质。
即使很多点有相同的 $s_u$，也就是相同的 $\lambda_u$，依然没有问题。
13. 单个重链节点是一个仿射变换
考虑点 $u$。
设所有轻儿子的有理函数之和为
$$ \frac{B_L}{D_L}. $$
没有轻儿子时取
$$ B_L=0,\qquad D_L=1. $$
设重儿子的有理函数为输入
$$ y. $$
根据定义 (11)，
$$ R_u = \frac{ z_u+y+\frac{B_L}{D_L} }{ x-\lambda_u }. $$
整理：
$$ R_u = \frac{ D_Ly+B_L+z_uD_L }{ (x-\lambda_u)D_L }. $$
所以点 $u$ 连同全部轻子树，可以看成一个对重儿子输入 $y$ 的仿射有理变换
$$ \boxed{ T_u(y) = \frac{A_uy+B_u}{D_u}, } \tag{19} $$
其中
$$ \boxed{ \begin{aligned} A_u&=D_L,\\ B_u&=B_L+z_uD_L,\\ D_u&=(x-\lambda_u)D_L. \end{aligned} } \tag{20} $$
关键观察是：
- $A_u,D_u$ 完全不依赖 $z$；
- 只有 $B_u$ 关于 $z$ 线性。
14. Compress：纵向合并一段重链
设上面一段对应
$$ T_1(y) = \frac{A_1y+B_1}{D_1}, $$
下面一段对应
$$ T_2(y) = \frac{A_2y+B_2}{D_2}. $$
复合：
$$ T_1(T_2(y)) = \frac{ A_1\frac{A_2y+B_2}{D_2}+B_1 }{ D_1 }. $$
整理得
$$ T_1(T_2(y)) = \frac{ A_1A_2y+A_1B_2+B_1D_2 }{ D_1D_2 }. $$
所以 compress 合并为
$$ \boxed{ \begin{aligned} A&=A_1A_2,\\ B&=B_1D_2+A_1B_2,\\ D&=D_1D_2. \end{aligned} } \tag{21} $$
仍然只有常数次多项式乘法。
当一条重链一直压到最底端时，底端输入为
$$ y=0. $$
于是整棵树最终得到
$$ R_1=\frac B D. $$
其中
$$ D=Q, \qquad B=N_z. $$
15. 一个大小 $m$ 的块只需要 $O(M(m))$
每个合并块对应一组互不相交的原树顶点。
若块中一共包含 $m$ 个原树点，则：
$$ \deg D=m, $$
而
$$ \deg B<m, \qquad \deg A\le m. $$
因为所有分母本质上都只是这个块中
$$ (x-\lambda_v) $$
的乘积。
rake 和 compress 每次只需要常数次、总次数 $O(m)$ 的多项式乘法。
因此一个大小为 $m$ 的合并结点的成本为
$$ \boxed{O(M(m)).} \tag{22} $$
这里已经没有任何额外的“块内乘积树/余式树”。
这正是相对于前面的点分治 $O(M(n)\log^2 n)$ 做法少掉一个 $\log$ 的原因。
16. 真正关键：必须全局平衡
如果只是普通重链剖分，然后“每条重链各自平衡”，还不能直接推出总高度 $O(\log n)$。
因为理论上可能：
- 跨过 $O(\log n)$ 条轻边；
- 每条链又贡献 $O(\log n)$；
从而看上去可能是 $O(\log^2 n)$。
所以需要带权平衡。
17. 带权平衡二叉树
考虑一组按固定顺序排列的原子，原子 $i$ 有正权重 $w_i$。
总权重
$$ W=\sum_iw_i. $$
我们可以建立一棵保持顺序的二叉合并树，使得权重为 $w_i$ 的原子深度为
$$ \boxed{ O\left(1+\log\frac W{w_i}\right). } \tag{23} $$
构造方式很简单：
每次取覆盖当前区间权重中点的原子，将：
- 左边区间递归；
- 当前原子；
- 右边区间递归；
用至多两个二元结点合并起来。
某个原子每多向下递归一层，其所在区间总权重至少减半。
因此深度就是
$$ O\left(1+\log\frac W{w_i}\right). $$
18. 对轻儿子做带权 rake
在点 $u$ 处，每个轻儿子 $v$ 的整个子树视作一个原子，权重为
$$ s_v. $$
这些轻子树总大小至多
$$ w_u-1. $$
用上述带权平衡树进行 rake。
于是轻儿子 $v$ 的子树信息合并到 $u$ 的“重链原子”时，其深度为
$$ O\left( 1+\log\frac{w_u}{s_v} \right). \tag{24} $$
19. 对重链做带权 compress
考虑一条重链
$$ u_1,u_2,\dots,u_k, $$
链头为 $r=u_1$。
每个重链节点 $u_i$ 连同其全部轻子树，作为一个原子。
它的权重正好是
$$ w_{u_i}. $$
由于相邻节点满足
$$ u_{i+1}=h(u_i), $$
有
$$ w_{u_i}=s_{u_i}-s_{u_{i+1}}. $$
所以望远镜求和：
$$ \boxed{ \sum_{u\text{ 在这条重链上}}w_u=s_r. } \tag{25} $$
因此按 $w_u$ 建带权平衡 compress 树后，原子 $u$ 在这条链中的深度是
$$ O\left( 1+\log\frac{s_r}{w_u} \right). \tag{26} $$
20. 为什么全局高度只有 $O(\log n)$
考虑一条从某个底层块不断向整棵树根部走的路径。
假设跨越了一条轻边
$$ u\to v, $$
其中 $v$ 是 $u$ 的轻儿子。
设 $u$ 所在重链的链头为 $r$。
从 $v$ 的整棵子树信息，走到链头 $r$ 的完整信息，需要：
在 $u$ 的 rake 树里，从轻儿子 $v$ 合并进去：
$$ O\left( 1+\log\frac{w_u}{s_v} \right); $$
在重链 compress 树里，从原子 $u$ 合并到链头：
$$ O\left( 1+\log\frac{s_r}{w_u} \right). $$
相加：
$$ O\left( 1+ \log\frac{w_u}{s_v} + \log\frac{s_r}{w_u} \right) = O\left( 1+\log\frac{s_r}{s_v} \right). $$
由于 $v$ 是轻儿子，而重儿子大小最大，所以必有
$$ s_v\le \frac{s_u-1}{2}<\frac{s_u}{2}\le\frac{s_r}{2}. $$
因此常数 $1$ 可以吸收进对数：
$$ \boxed{ O\left(\log\frac{s_r}{s_v}\right). } \tag{27} $$
现在沿路径不断跨轻边。
若连续涉及的子树大小为
$$ S_0<S_1<\cdots<S_k\le n, $$
总代价是
$$ O\left( \log\frac{S_1}{S_0} + \log\frac{S_2}{S_1} +\cdots+ \log\frac n{S_k} \right). $$
望远镜相消：
$$ = O\left(\log\frac n{S_0}\right) = O(\log n). $$
因此整个 rake/compress 合并树的高度满足
$$ \boxed{O(\log n).} \tag{28} $$
这个证明是整个 $O(M(n)\log n)$ 上界里最容易被粗略带过、但实际上必须说清楚的一步。
21. 从 $z\mapsto N_z$ 转置回来
前面的合并过程定义了一个线性映射
$$ z\mapsto B=N_z. $$
我们其实不需要真的把 $z_1,\dots,z_n$ 当作符号变量展开。
只需：
- 正向计算所有固定的 $A,D$；
- 在根部给 $B$ 一个伴随向量；
- 顺着合并树反向传播；
- 最终得到每个 $z_u$ 的伴随值，也就是 $h_u$。
22. 根部的伴随向量
我们知道
$$ \sum_uz_uh_u = [x^{-1}] \frac{P(x)B(x)}{Q(x)}. $$
令
$$ P^\vee(t) = t^{n-1}P(t^{-1}), $$
$$ Q^\vee(t) = t^nQ(t^{-1}). $$
因为 $Q$ 首一，所以
$$ Q^\vee(0)=1. $$
定义
$$ \boxed{ C(t) = \frac{P^\vee(t)}{Q^\vee(t)} \bmod t^n = \sum_{j=0}^{n-1}c_jt^j. } \tag{29} $$
若
$$ B(x)=\sum_{j=0}^{n-1}B_jx^j, $$
则有
$$ \boxed{ [x^{-1}] \frac{PB}{Q} = \sum_{j=0}^{n-1}c_jB_j. } \tag{30} $$
证明只需令 $t=1/x$：
$$ \frac{P(1/t)B(1/t)}{Q(1/t)} = t \frac{P^\vee(t)}{Q^\vee(t)} \sum_jB_jt^{-j}. $$
$x^{-1}$ 就是 $t^1$，因此对应系数恰为
$$ \sum_jc_jB_j. $$
所以根结点 $B$ 的伴随向量就是
$$ \boxed{\bar B=(c_0,c_1,\dots,c_{n-1}).} $$
求 $C$ 只需要一次形式幂级数求逆与一次乘法：
$$ O(M(n)). $$
23. 转置多项式乘法
后面的所有反向传播最终都归结到：
正向有
$$ Y=XK. $$
设
$$ X=(X_0,\dots,X_{a-1}). $$
若 $\bar Y$ 已知，则
$$ \bar X_i = \sum_j K_j\bar Y_{i+j}. \tag{31} $$
这就是一个相关运算。
将 $K$ 的系数反转后做一次普通卷积，再截取对应区间即可。
因此
$$ \boxed{ Y=XK \quad\text{的转置也只需}\quad O(M(m)). } \tag{32} $$
我们把这个操作记作
$$ \operatorname{Mul}_K^{\mathsf T}. $$
24. Rake 的反向传播
正向：
$$ B=B_1D_2+B_2D_1. $$
因此反向：
$$ \boxed{ \begin{aligned} \bar B_1 &= \operatorname{Mul}_{D_2}^{\mathsf T}(\bar B),\\ \bar B_2 &= \operatorname{Mul}_{D_1}^{\mathsf T}(\bar B). \end{aligned} } \tag{33} $$
由于 $D_1,D_2$ 都是固定的，所以没有其他关于 $z$ 的传播。
25. Compress 的反向传播
正向：
$$ B=B_1D_2+A_1B_2. $$
因此
$$ \boxed{ \begin{aligned} \bar B_1 &= \operatorname{Mul}_{D_2}^{\mathsf T}(\bar B),\\ \bar B_2 &= \operatorname{Mul}_{A_1}^{\mathsf T}(\bar B). \end{aligned} } \tag{34} $$
同样只需要两次转置卷积。
26. 单点处得到 $h_u$
在一个重链原子中，
$$ B_u=B_L+z_uD_L. $$
于是
$$ \frac{\partial B_u}{\partial z_u}=D_L. $$
因此
$$ \boxed{ \bar z_u = \langle\bar B_u,D_L\rangle. } \tag{35} $$
而根据总目标 (13)，
$$ \bar z_u=h_u. $$
所以
$$ \boxed{ h_u= \langle\bar B_u,D_L\rangle. } \tag{36} $$
同时，由于
$$ B_L\to B_u $$
只是恒等嵌入，所以将 $\bar B_u$ 截取到 $B_L$ 的有效系数范围以后继续向 rake 树传播即可。
因此我们在整个过程中从来不用显式构造关于所有 $z_u$ 的多项式 $B$。
只需要保存：
- 每个合并块的 $A$；
- 每个合并块的 $D$；
- 反向传播时的一份伴随多项式。
27. 如何快速构造 $P(x)$
还有一个预处理问题：
$$ P(x) = \sum_{i=0}^{n-1} c_ix^{\underline i}. $$
不能花 $O(n^2)$ 逐项展开。
定义对于区间 $[\ell,r)$：
$$ B_{\ell,r}(x) = \prod_{j=\ell}^{r-1}(x-j), $$
以及
$$ S_{\ell,r}(x) = \sum_{i=\ell}^{r-1} c_i \prod_{j=\ell}^{i-1}(x-j). $$
若
$$ m=\left\lfloor\frac{\ell+r}{2}\right\rfloor, $$
则
$$ \boxed{ B_{\ell,r} = B_{\ell,m}B_{m,r}, } \tag{37} $$
而
$$ \boxed{ S_{\ell,r} = S_{\ell,m} + B_{\ell,m}S_{m,r}. } \tag{38} $$
最终
$$ P=S_{0,n}. $$
每层区间次数总和是 $O(n)$，所以复杂度为
$$ \boxed{O(M(n)\log n).} \tag{39} $$
28. 总复杂度证明
现在来看整个 Top Tree 合并树。
设某个合并块 $C$ 含有
$$ m_C $$
个原树顶点。
前面已经证明：
$$ \text{处理 }C\text{ 的正向/反向代价} = O(M(m_C)). $$
由于整个合并树高度是
$$ O(\log n), $$
而在同一深度上，各个块对应的原树顶点集合互不相交，所以
$$ \sum_{C\text{ 同层}}m_C\le n. $$
利用
$$ M(k)/k $$
单调不减：
$$ M(m_C) \le \frac{m_C}{n}M(n). $$
因此同一层总代价
$$ \sum_C M(m_C) \le \frac{M(n)}n \sum_Cm_C \le M(n). $$
一共 $O(\log n)$ 层，所以
$$ \boxed{ \sum_CM(m_C) = O(M(n)\log n). } \tag{40} $$
加上：
- 构造 $P$：$O(M(n)\log n)$；
- 构造 $Q$：已包含于合并结构，也可单独 $O(M(n)\log n)$；
- 求 $P^\vee/Q^\vee\bmod t^n$：$O(M(n))$；
- 正向建立 $A,D$：$O(M(n)\log n)$；
- 反向传播：$O(M(n)\log n)$。
所以总时间
$$ \boxed{ O(M(n)\log n). } $$
空间上若保存整棵合并树的 $A,D$，同样按层计算总系数规模：
$$ \boxed{ O(n\log n). } $$
29. 最后恢复原问题答案
反向传播得到所有
$$ h_u. $$
回忆
$$ h_u = \sum_i b_{i+1}(n-1-i)! E_{i,u}. $$
而
$$ D_{i,u}=t_uE_{i,u}. $$
因此根据最初的染色方案计数，
$$ \boxed{ f(u) = \frac{s_ut_u}{H}h_u. } $$
其中
$$ H=\prod_vs_v, $$
$$ t_1=1, $$
$$ t_u=t_{\operatorname{fa}_u}s_{\operatorname{fa}_u}. $$
由于
$$ 1\le s_u\le n<10^9+7, $$
这里所有 $s_u$ 在模 $10^9+7$ 下都非零，所以 $H^{-1}$ 合法。
30. 整个算法的逻辑链
如果把整篇题解压缩成一条主线，就是：
$$ \boxed{ \begin{array}{c} \text{官方 }O(n^2)\text{ 染色 DP}\\[2mm] \Downarrow\\[2mm] D_{i,u}/t_u\\[2mm] \Downarrow\\[2mm] E_{i,u} = (\lambda_u-i+1)E_{i-1,u} + E_{i-1,\operatorname{fa}_u}\\[2mm] \Downarrow\\[2mm] E_{i,u} = \left( x^{\underline i}\operatorname{quo}A_u \right)(\lambda_u)\\[2mm] \Downarrow\\[2mm] P(x)=\sum_i b_{i+1}(n-1-i)!x^{\underline i}\\[2mm] \Downarrow\\[2mm] h_u= (P\operatorname{quo}A_u)(\lambda_u)\\[2mm] \Downarrow\\[2mm] h_u=[x^{-1}]P/G_u\\[2mm] \Downarrow\\[2mm] R_u= \dfrac{z_u+\sum R_v}{x-\lambda_u}\\[2mm] \Downarrow\\[2mm] \sum z_uh_u=[x^{-1}]PR_1\\[2mm] \Downarrow\\[2mm] \text{rake/compress 线性电路}\\[2mm] \Downarrow\\[2mm] \text{带权全局平衡，深度 }O(\log n)\\[2mm] \Downarrow\\[2mm] \text{转置电路一次求全部 }h_u\\[2mm] \Downarrow\\[2mm] \boxed{O(M(n)\log n)}. \end{array} } $$
31. 实现时最容易踩的几个坑
有几个地方我觉得正式实现时值得特别标出来。
第一，千万不要真的给每个原树节点维护完整的子树分子分母。
那样链上会出现
$$ 1+2+\cdots+n, $$
又退回二次。
只维护全局平衡合并树里的多项式。
第二，$\lambda_u$ 永远定义为
$$ \lambda_u=n-s_u, $$
其中 $s_u$ 是原树子树大小。
Top Tree 分块以后不要重新计算。
第三，rake/compress 过程中绝对不要约分。
统一保留分母因子
$$ (x-\lambda_v) $$
的乘积。
这样即使两个点有相同的 $\lambda$，算法也完全成立。
第四，compress 是有顺序的。
若上块为 $T_1$，下块为 $T_2$，必须计算
$$ T_1\circ T_2, $$
不能交换。
因此重链上的带权平衡树必须保持原顺序。
第五，反向乘法不是普通的“再乘一次”。
若正向
$$ Y=XK, $$
那么反向是相关
$$ \bar X_i=\sum_jK_j\bar Y_{i+j}. $$
实现时需要：
- 反转 $K$；
- 做卷积；
- 截取正确区间。
第六，所有多项式都最好严格记录逻辑长度，而不是只依靠去掉尾零后的 vector.size()，否则转置时的截取范围很容易错。
32. 一个较适合放在正式题解结尾的总结
本题官方 $O(n^2)$ 解法已经揭示了一个非常特殊的二维递推：
$$ D_{i,u} = (n-i+1-s_u)D_{i-1,u} +s_{\operatorname{fa}_u}D_{i-1,\operatorname{fa}_u}. $$
对祖先子树大小积进行归一化后，这一递推与下降阶乘在一族“先对祖先多项式取商、再在当前点求值”的线性泛函下满足完全相同的递推，因此可以将所有位置权值一次性合并为一个多项式 $P$，将原问题化为 $n$ 个祖先链取商查询。
进一步利用
$$ (P\operatorname{quo}A_u)(\lambda_u) = [x^{-1}] \frac{P}{\prod_{v\in\operatorname{path}(1,u)}(x-\lambda_v)}, $$
这些查询可以统一写成一个树形有理函数 DP 的转置。
该有理函数 DP 的轻子树合并是 rake：
$$ (B_1,D_1),(B_2,D_2) \mapsto (B_1D_2+B_2D_1,D_1D_2), $$
重链合并是 affine transform 的 compress：
$$ (A_1,B_1,D_1),(A_2,B_2,D_2) \mapsto (A_1A_2,B_1D_2+A_1B_2,D_1D_2). $$
每个大小 $m$ 的块只需 $O(M(m))$ 时间。
再以
$$ w_u=s_u-s_{h(u)} $$
作为重链原子的权重，对 rake 与 compress 都做带权平衡，可以证明整个合并树全局高度为 $O(\log n)$。
最后转置整条线性电路，即可一次求出全部答案。
因此总复杂度为
$$ \boxed{O(M(n)\log n)} $$
时间，
$$ \boxed{O(n\log n)} $$
空间。