题解：P16355 「Diligent-OI R3 C」彼方へ、名もなき海辺より

· · 题解

考虑对于每一个大小为 x 的连通块，块内每一个点向其他点连一条边，那么这个连通块一定是一个基环树。因此把连通块计数转化为环计数。

因为本题图的生成方式很特别，所以环一定由原树上一条深度递增的链与一条返祖边构成，不然肯定有一个点要连出两条边。

那么可以发现没有两张图是存在一个点 u 选择链接的点不同且最后的图一样。因为我们可以对任意一个图进行以下操作来还原序列：每次选择度数为 1 的点 u ，以该点为端点的边为 (u,v)，那么 u 选择的点为 v；最后肯定剩下若干个环，将环上深度最大的点 y 和环上深度最小的点 x 之间的连边 (x,y) 断开，并记 y 选择 x，接下来继续按上一步做即可。

记环点集为 S，点 u 的深度（到 1 经过边数）与儿子数量这和为 c_u，那么这个环对答案的贡献为 \prod_{u \notin S}c_u，也就是钦定 S 内点的连边后，其他点任意连边的答案，如果记 T=\prod_u c_u，那么答案就可以表示为 \dfrac{T}{\prod_{u \in S} c_u}，至此有 O(n^2) 做法。

考虑一个点的贡献：不妨记点 u 的祖先集合为 P_u，那么 u 点作为环上深度最大点的贡献为

\begin{aligned} &\sum_{v \in P_u}\dfrac{T}{ \prod_{ w\in P_u \setminus P_v} c_v}\\ =&\sum_{v \in P_u}T\dfrac{\prod_{ w\in P_v}c_w}{\prod_{ w\in P_u}c_w }\\ =&\dfrac{T}{\prod_{ w\in P_u}c_w}\sum_{v\in P_u}\prod_{w\in P_v}c_w \end{aligned} 时间复杂度 $O(n)$。