考虑 $x$ 子树内部的构成，我们要减去的是每个子树的平方和，这和 $\prod a$ 是不联系的。于是求出 $g_i$ 表示 $i$ 个点的 $\prod a$ 和，在乘上 $x$ 连边的方案数（$x=1$ 比较特别，单独考虑）。
然后令 $f_i$ 表示 $i$ 个点树的方案数，乘平方和。这个拆开 exp 就行了。
时间复杂度 $O(n\log^2 n)$。 提交记录：Submission #98626 - QOJ.ac。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #1017 for Problem #3087. Find the LCA
Type: Editorial
Status: Open
Posted by: Qiuly
Posted at: 2026-02-14 02:06:23
Last updated: 2026-02-14 02:06:33
题解
Comments
No comments yet.