本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-26 17:25:24

T4

100pts:

按二进制位枚举，对于第j位：

设$\sum _{l_1 \le r_1 \le i} XOR(l_1,r_1)$的值为$f1[i][j]$ 。如果第j位为0，$f1[i][j] = f1[i-1][j] + sum1[i][j] \times 2^j$，如果第j位为1，$f1[i][j] = f1[i-1][j] + sum0[i][j] \times 2^j$ ，其中$sum0/1[i][j]= \sum _{l \le i} XOR(l,i)$，只考虑第j位。

然后把$f1$的每一位综合起来，得到$f1[i]= \sum f1[i][j]$

设$\sum _{l_1 \le r_1 < l_2 \le r_2 \le i} XOR(l_1,r_1) \times XOR(l_2,r_2)$的值为$f2[i][j]$ 。如果第j位为0，$f2[i][j] = f2[i-1][j] + sum1[i][j] \times 2^j$，如果第j位为1，$f2[i][j] = f2[i-1][j] + sum0[i][j] \times 2^j$ ，其中$sum0/1[i][j]= \sum _{l \le i} f1[l-1] \times XOR(l,i)$，只考虑第j位。

然后把$f2$的每一位综合起来，得到$f2[i]= \sum f2[i][j]$

设$\sum _{l_1 \le r_1 < l_2 \le r_2 < l_3 \le r_3 \le i} XOR(l_1,r_1) \times XOR(l_2,r_2) \times XOR(l_2,r_2)$的值为$f3[i][j]$ 。如果第j位为0，$f3[i][j] = f3[i-1][j] + sum1[i][j] \times 2^j$，如果第j位为1，$f3[i][j] = f3[i-1][j] + sum0[i][j] \times 2^j$ ，其中$sum0/1[i][j]= \sum _{l \le i} f2[l-1] \times XOR(l,i)$，只考虑第j位。

然后把$f3$的每一位综合起来，得到$f3[i]= \sum f3[i][j]$，即为答案

另一种统计答案的方式是正着求$f2$，倒着求$f1$，然后枚举$r_2$的位置。

70pts:

设$\sum _{l_1 \le r_1 \le i} XOR(l_1,r_1)$的值为$f1[i]$ 。

$n^2$正着倒着分别求$f1$，然后$n^2$枚举$l_2$，$r_2$即可。

t5

• 25pts：N^3 枚举 (以哪个为根，dfs，枚举颜色)
• 50pts：N^2 枚举 (优化颜色枚举)
• 菊花：记录所有颜色的数量，对每个颜色计数
• 链：对每个颜色维护一个序列，复杂度O(n)，分别计数
• 100pts：对每个颜色维护一个虚树，动态规划
  • 设 $dp[u][0/1/2]$ 表示u到u的子树中路径包含0~2条关键边的点数
  • 记录答案