自动搬运

查看原文

来自洛谷，原作者为

	min_inf 你路过的 与我追逐的 我会等它们重合

搬运于2025-08-24 23:09:08，当前版本为作者最后更新于2025-01-31 21:22:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

你们萌熊 X 组最后一题都这么唐的吗。。

首先这个 $a_i$ 乘起来的权值看上去有点无敌，我们不管这个，当他是指定 $2^k$ 个权值。

然后我们从下往上 DFS 的时候算一下子树间的贡献，需要做的事情是对一个集合内 $x\gets x|y$ 以及对两个集合算 $\sum w_{x|y}$ 并合并这两个集合。

考虑根号分治，每个集合维护 $\le B$ 个零散的值和一些关于其他值的信息，合并的时候分别暴力合并，散块超过了 $B$ 就暴力重构一下，总共只会重构 $\frac nB$ 次。

考虑怎么算合并的两个集合之间的贡献，散块的贡献暴力求复杂度是只有 $O(nB)$ 的，整块每次暴力 FWT 求，散块一个点到整块的贡献是形如 $\sum a_yb_{x|y}$ 的，就是 这个题，每次重构大块的时候倒着做一下 FWT 预处理就行了。

时间复杂度 $O(n\sqrt{k2^k})$。code