P9619||【主题库】生成树

· · 题解

第一眼：生成树计数？矩阵树定理才绿题？

仔细一看：无向完全图，行了，有公式。

题意

有 𝑛 个节点的无向完全图，第 𝑖 个节点的点权为 𝑎_i。对于 𝑢,𝑣 之间的一条边，贡献为 𝑎_𝑢\oplus𝑎_𝑣。每棵生成树的价值是其全部边的边权和，求原图全部生成树的价值和。

思路

首先因为是完全图，那么意味着最后统计贡献时，每条边都会被计算相同的次数。

那么对于一个 n 个点的完全图：

种类 数量
点 n
边 \frac{n\times (n-1)}{2}
生成树 n^{n-2}
每个生成树边数 n-1

简单算一下：

\text{每个生成树边数} \times \text{完全图生成树数} \div \text{完全图总边数}=\text{每条边贡献次数}\\ \frac{(n-1)\times n^{n-2}}{\frac{n\times(n-1)}{2}}=2\times\frac{n^{n-2}}{n}=2\times n^{n-3}

特例是只有一个或两个点时：只有一个点答案为 0，两个点答案就是唯一的那条边的权值。

剩下的就是开桶算每一位是几的数有几个，求总贡献，之后搞个快速幂算一下每条边被计算的次数，乘上就行。

（long long 警告。）

（代码太烂不建议看）