题解：P11648 【MX-X8-T7】「TAOI-3」2236 A.D.

· · 题解

你们萌熊 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