非常好题目。
思路
可以发现限制最严的一定是两个叶子的联通性。
我们不妨把一个叶子向外起到联通性作用的路径称为有用的路径。
也就是这个叶子走这条路径一定可以两步以内到达任意点。
这个路径集合有什么作用呢。
有一个性质：整个集合的路径的交最终会形成一个连通块。
那么我们就可以进行求解方案数。
考虑容斥。
我们设 \(dp_{1,i}\) 为联通块内强制有 \(i\) 这个点，设 \(dp_{2,i}\) 为联通块内强制有 \(i\) 这条边。
那么：
\[ans=\sum dp_{1,i}-\sum dp_{2,i} \]如何求解？
首先考虑边的情况。
我们可以设 \(f_i\) 为至少有 \(i\) 个叶子不与这条边联通，\(sz_i\) 表示 \(i\) 的子树大小，\(yz_i\) 表示 \(i\) 的叶子数量。
那么：
\[f_{i+j}=\sum_{i=0}^{yz_x}C_{yz_x}^i 2^{i\times(sz_x-1)-\frac{i\times(i-1)}{2}}\sum_{j=0}^{yz_y}C_{yz_y}^j 2^{j\times(sz_y-1)-\frac{j\times(j-1)}{2}} \]当然还要乘其他不重要的边的方案数，也是一个二的次幂。
暴力做是平方的。
容易发现可以多项式优化。
然后考虑点的情况。
同样可以设 \(f_i\) 为至少有 \(i\) 个叶子不与这个点联通。
那么加入一颗子树的代价是：
\[f_{i+j}=\sum f_i\sum_{j=0}^{yz_y}C_{yz_y}^j 2^{j\times(sz_y-1)-\frac{j\times(j-1)}{2}} \]同样是卷积形式，可以多项式优化。
最终复杂度：\(O(n^2 \log n)\)。
标签：sz,联通,题解,sum,times,yz,P10064,SNOI2024,dp From： https://www.cnblogs.com/JiaY19/p/18026233