LOJ3399 「2020-2021 集训队作业」Communication Network
LOJ 分析 感觉和 WC2019 数树 的 $op = 1$ 基本一致，如果不会可以戳 这里。 我们还是套用 $\displaystyle |S| \prod_{i = 1}^k na_i$ 有着清晰的组合意义：从 $S$ 中选择一条边，再从每个连通块中选择一个点，每个点产生 $n$ 的乘积贡献。我们要求所有 $S$ 的贡献的总和。 考虑 DP。设 $f_{u, 0/1, 0/1}$ ...
LOJ 分析 感觉和 WC2019 数树 的 $op = 1$ 基本一致，如果不会可以戳 这里。 我们还是套用 $\displaystyle |S| \prod_{i = 1}^k na_i$ 有着清晰的组合意义：从 $S$ 中选择一条边，再从每个连通块中选择一个点，每个点产生 $n$ 的乘积贡献。我们要求所有 $S$ 的贡献的总和。 考虑 DP。设 $f_{u, 0/1, 0/1}$ ...
Luogu LOJ orz laofu！!1 分析 $op = 0$ 只需要统计两棵树有多少条重边即可。假设有 $c$ 条，答案即为 $y^{n - c}$。 $op = 1$ 先特判掉 $y = 1$ 的情况，答案为 $n^{n - 2}$。 我们要求的是 考察每个连通分量。一个大小为 $a$ 的连通分量会产生 $\frac{n^2 y}{1 - y} a^2$ 的乘积贡献，而 $a$...
Codeforces Luogu 算法一 分析 设树边的权值为 $x$，非树边的权值为 $1$，然后矩阵树定理。设得到的多项式为 $F(x)$，那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。 然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式，所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$，然后解方程组解出系数即可...
Codeforces Luogu 分析 我们把每个连通块看成一个点，然后用 Prufer 序列计数。那么方案数为 用并查集求出连通块个数及每个连通块的大小即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ============...
LOJ 分析 树相等于一个左部点是深度为奇数的点、右部点是深度为偶数的点的二分图。 首先需要在 $n-1$ 个点中选出 $k-1$ 个作为深度为奇数的点（$1$ 的深度一定为奇数）。 将深度为奇数的点作为左部点、深度为偶数的点作为右部点，两部分间两两连边，则问题变为求生成树个数。 考虑 Prufer 序列，则左部点出现了 $n-k-1$ 次、右部点出现了 $k-1$ 次，故生成树个数为 $k...