TopCoder 13369 TreeDistance / CF917D Stranger Trees 题解

大致题意：给你一棵 \(n\) 个点的树，求有多少棵 \(n\) 个点的树与它的边集交大小为 \(k\) 。

\(n\le 100\) 。

其实这个题和”数树”很像啊。

法 \(1\) ：考虑 \(matrix-tree\) 定理。

我们直接构造一个完全图，不在原树上的边边权为 \(1\) ,否则边权为 \(x\) ，这样就能求出一个多项式，\(x^k\) 的系数即为答案。

直接重载多项式跑行列式不太行？我们考虑插值计算即可。

复杂度 \(O(n^4)\) 。

法 \(2\) ：容斥/二项式反演，组合意义。

考虑 \(g_i\) 为所有钦定 \(i\) 条边的方案能造出的树的个数和。

\(f_i\) 为与原树交大小为 \(i\) 的树个数。

则 \(g_i=\sum f_jC(j,i)\) ，即 \(f_k=\sum g_i (-1)^iC(i,k)\) 。

考虑 \(g_i\) 怎么算。假设已经钦定了一个大小为 \(t\) 的边集，这些边形成了 \(n-t\) 棵树，令每一棵大小分别为 \(a_1,a_2,…,a_{n-t}\) 。

则一个经典结论是方案为 \(n^{-2}\prod (a_in)\) 。

\(\prod a_i\) 的经典组合意义就是在每个连通块选恰好一个点。

所以设计 \(dp_{i,j,0/1}\) 表示子树 \(i\) 内，钦定了 \(j\) 条边，\(i\) 所在联通块是否选了一个点，总方案数。

\(O(n^2)\) 求出，统计答案即可。

原文地址：http://www.cnblogs.com/Sakurajima-Mai/p/16829249.html