8.11

神金诈骗题。

最难的是想到只用分一个个的，因为如果把子树分开，和不分是等价的。

问题就转化成了一个数可以把它变小，问最大的或。

注意到 $\sum s_i\le10^6$，所以直接枚举每棵树留几个节点即可。

负收益的情况：

考虑一对(i,j)

i在j前的要求

==> x>=max(a_i,a_j+a_i-b_i)

j在i前的要求

==> x>=max(a_j,a_j+a_i-b_j)

哪个更小哪个更优。

也就是 b_i>b_j 时，i 更优

转化到树上，如果一个点的优先级是最高的，那么处理完它的父节点之后一定会立即更新它。可以把它和它的父节点合并起来，合成一个新点，再计算它的优先级，这个动态维护的过程可以用优先队列等方法。

容斥思想，枚举子集。

$f_S$ 表示的是原数组，$S$ 是把每一维压起来，$g_S$ 是前缀和。

$g_S=\sum_{T\sub S} f_T$。

$f_S=\sum_{T\sub S} (-1)^{|S-T|}\times g_T$。