二项式反演：
\[f(n)=\sum\limits_{i\ge n}{i\choose n}g(i)\iff g(n)=\sum\limits_{i\ge n}(-1)^{i-n}{i\choose n}f(i) \]设 \(f(k)\) 表示在新树上钦定 \(k\) 条边与原树相同的方案数，\(g(k)\) 表示恰有 \(k\) 条边与原树相同的树的个数（答案），则只需求出 \(f\)。
考虑求 \(f(k)\)。若连上某 \(k\) 条边后形成 \(m\) 个连通块，第 \(i\) 个连通块大小为 \(a_i\)，则钦定这 \(k\) 条边与原树相同的方案数为 \(n^{m-2}\prod a_i\)。
考虑 \(\prod a_i\) 的组合意义，发现就是从每个连通块里选一个点的方案数，
所以如果没有那个 \(n^{m-2}\)，就是要求选定 \(k\) 条边，再从形成的每个连通块里选一个点的方案数，
把 \(n^{m-2}\) 看成形成了 \(m\) 个连通块的方案的权值，则 \(f(k)\) 就是选了 \(k\) 条边的每种方案的权值和。
Sol 1
设 \(f_{u,i,0/1}\) 表示在 \(u\) 子树中选择 \(i\) 条边，在 \(u\) 所在的连通块中是/否已经选了一个点的方案的权值和，树上背包转移即可。
空间开不下，所以把 \(u\) 的孩子 \(v\) 合并到 \(u\) 上之后，把 \(v\) 的状态占用的内存释放掉，这样空间是 \(O(n)\) 的。
Sol 2
设 \(F(x)=\sum\limits_{i=0}^{n-1}f(i)x^i\)（\(F\) 是 \(f\) 的 OGF），考虑拉插出 \(F\) 的系数 \(f\)。考虑如何求 \(F\) 的点值。
规定在之前的基础上，每连一条边方案的权值就乘上 \(x\)，即连 \(k\) 条边形成 \(m\) 个连通块的方案的权值为 \(n^{m-2}x^k\)，
则 \(F(x)\) 就是所有方案的权值和（没有选择边数限制），可以用上面的 DP 去掉第二维解决。
这样任取 \(n\) 个互不相同的 \(x_i\)，求出对应的 \(F(x_i)\)，拉格朗日插值即可算出各项系数。
拉格朗日插值：
\[F(x)=\sum\limits_{i=1}^nF(x_i)\prod\limits_{j\ne i}\dfrac{x-x_j}{x_i-x_j} \] 标签：方案,连通,limits,T4,权值,条边,sum,前瞻 From： https://www.cnblogs.com/5k-sync-closer/p/18445837