以下题解由WuHongxun（出题人）发布的视频题解进行文本还原。

A：Last mile of the way

算法一

对每个询问暴力背包DP即可。期望得分10分。

算法二

用 $f[x][s]$ 表示以 $x$ 为根的子树中取一些大小和不超过 $s$ 的节点，最大权值和为多少。转移考虑逐个将 $x$ 的子节点合并到 $x$ 子树中，合并子节点 $c$ 时：

$$f[x][s] \leftarrow f[c][s'] + f[x][s - s']$$

复杂度 $O(ns^2)$。期望得分30分。

算法三

树是一条链，每个询问相当于询问链的一个后缀的背包。

$f[x][s]$ 表示后 $x$ 个结点取大小和不超过 $s$ 的节点，最大权值和是多少。

每次加入一个物品：

$$f[x][s] \leftarrow f[x][s – size[x]] + weight[x]$$

结合算法二期望得分50分。

算法四

之前做法的瓶颈在于合并子树的复杂度较高。可以用启发式合并的trick，即每次合并时暴力DFS物品较少的子树。

比如一个点有多个孩子，其中一个孩子物品最多，则合并时把最大的这个孩子的DP数组直接拷贝到父亲上，对于其它孩子暴力DFS，把这些物品一个个加进来。

显然每次加入物品是 $O(s)$ 的。每加一次物品，由于它不在最大的子树里，它所在的集合大小至少会乘2，由于总的集合大小为 $n$，所以每个物品最多被加 $O(\log n)$ 次。复杂度 $O(ns\log n)$。期望得分100分。

B：Reason For Living

算法一

最大化生成森林的边数，等价于选一个极大的生成森林，即无法加入一条边使得生成森林更大。

暴力用并查集维护，由于每次至少会删去一条边，这样复杂度是 $O(m^2)$。

期望得分40分。如果不会并查集，用其它方法可能可以得到20分。

算法二

考虑一条边一条边往图中加，维护若干个生成森林，显然每条边应加到第一个两端点不连通（或者说加入后生成森林里没有环）的森林中。

每个生成森林都用一个并查集维护，二分出第一个两端点不连通的并查集。显然使它们连通的并查集是一个前缀，因为我们每次取的是极大的生成森林。

现在的问题是，如果用 $m$ 个并查集，如果每一个生成森林都用一个并查集维护，是不是需要 $nm$ 个点？其实可以非常简单地处理，对于一个度数为 $d$ 的点，它最多只会在前 $d$ 个生成森林里出现，把这个点放到前 $d$ 个生成森林里。由于每条边最多给两个点的度数加1，所以所有并查集只需要 $2m$ 个点。

复杂度 $O(m\log m\cdot\alpha(n))$。期望得分80分。

算法三

见链接：http://oj.acyume.com/blogof/wuhongxun/blog/20

我也没懂，不过直接写80分算法可以100分：http://oj.acyume.com/submission/2410

C：World Of Our Own

算法一

按照题意暴力 $O(n^2)$ 模拟即可。期望得分30分。

算法二

$d\le 50$，观察数据生成方式，$A$ 中每一项只和上一项有关，由于前 $d+1$ 个数中必有两数相同，也就是 $A$ 会出现循环节然后一直循环下去，循环节第一次出现位置和长度均不超过 $d$。

利用循环节的性质，只对第一次出现循环节之前的部分和循环节进行模拟即可，复杂度 $O(nd)$。结合算法一期望得分70分。

算法三

这个过程可以看成在每次在 $A$ 的上方每个位置写上它下方和右下方的数的异或，并且每次长度减1。它等价于 $A$ 中每个点每次往上走一步或往左上走一步，有多少种方案走到这个点。假设 $A$ 中的点为 $i$（初始数列的第 $i+1$ 项），另一个点为 $j$（第 $j$ 个数列的第一项），那么 $i$ 点到 $j$ 点会往上走 $j$ 步，并且正好往左上走了 $i$ 步，也就是走上去的方案数正好是 $C_j^i$。

也就是第 $j$ 个数列的第一项实际上是 $C_j^0$ 个 $a_1$，$C_j^1$ 个 $a_2$，…，$C_j^i$ 个 $a_{i+1}$，…，$C_j^j$ 个 $a_{j+1}$ 异或起来。如果 $i$ 到 $j$ 有奇数种方案，那么 $i$ 到 $j$ 就有贡献，否则就没有贡献。也就是要考虑 $C_j^i$ 的奇偶性。

根据Lucas定理：

$$C_j^i\bmod 2=C_{\lfloor\frac{j}{2}\rfloor}^{\lfloor\frac{i}{2}\rfloor}\cdot C_{j\bmod 2}^{i\bmod 2}\bmod 2$$

实际上相当于每次把 $i,j$ 的二进制表示的最后一位 $i\bmod 2,j\bmod 2$ 取出来，然后删掉。$C_{j\bmod 2}^{i\bmod 2}=0$ 当且仅当 $j\bmod 2=0$ 而 $i\bmod 2=1$。那么 $C_j^i$ 为奇数当且仅当每个二进制位都没有这种情况，也就是 $i$ 的二进制中1的位是 $j$ 的二进制中1的位的一个子集，即

$$i\ \mathrm{and}\ j=i$$

对于每个 $j$ 的答案，记为 $b_j$，它等于所有满足 $i\ \mathrm{and}\ j=i$ 的 $a_i$ 的异或和。怎么做呢？

注意到这里的子集可以看成一个高维前缀和，可以看成数组 $a$ 有 $m$ 维，每一维都是 $0$ 或 $1$，表示下标的一个二进制位。我们要对 $a$ 求一个 $m$ 维的前缀和得到 $b$，$b_j$ 就是把 $j$ 中的一些 $1$ 的位变成 $0$ 得到 $i$ 的 $a_i$ 的和。

我们知道，二维前缀和有两种方法，第一种方法是这样：

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

实际上还有第二种方法，每次把一维做前缀和：

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        a[i][j] += a[i - 1][j];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        a[i][j] += a[i][j - 1];

现在我们同样用第二种方法。因为 $n\le 8\times 10^6$，下标的二进制只有 $23$ 位，所以可以令 $m=23$，依次枚举 $0,1,\cdots,22$ 每一维做前缀和即可：

for(int j = 0; j < 23; j++)
    for(int i = 0; i <= n; i++)
        if (i >> j & 1) a[i] ^= a[i ^ (1 << j)];

复杂度 $O(n\log n)$。期望得分100分。事实上这题可以用压位的trick进一步降低复杂度，不过这题直接这样实现就可以过了。