CF1779F

Mars_Dingdang · 2023-01-21 18:59:31 · 题解

翻译是我给的，但题解是翻译通过之后几天才写的，原因是口胡完了不想动代码。

题目大意

给定一棵 n(n\le 2\times 10^5) 个节点的树，第 i 个节点有非负权值 a_i\le 31。定义一次操作为：

• 选择一个节点 i，1\le i\le n。
• 计算以 i 为根的子树（包括 i 本身）内的所有节点权值的异或和 x。
• 将以 i 为根的子树（包括 i 本身）内的所有节点权值赋值为 x。

已知这一操作最多可以执行 2n 次。Mars 想知道是否可以通过执行若干次这一操作使得树上所有节点权值均为 0。

如果可以，输出第一行一个非负整数 q 表示操作次数，第二行为 q 个正整数，表示每次操作选择的节点编号 i；如果不可以，输出一行一个整数 -1。

你不需要最小化 q，输出任意一组解即可。

大体思路

记 sz_u 表示 u 为根的子树大小，son_u 表示 u 的儿子个数。

这题口胡之所以容易，是因为很快能够发现两个结论。

因此，对奇数大小的子树的根操作是无意义的，对偶数大小的子树的根节点最多操作两次（而且只有最后全部清零时才会操作两次），因此操作次数不超过 2n 是必然的。

然后，我们可以使用树形 DP 求解这一问题。这很明显是一个背包。

记 F(u,x,i) 表示考虑 u 的前 i 个儿子节点，能否是的以 u 为根的子树的点权异或和为 x。转移时枚举儿子节点 v_i 以及异或和即可，时间复杂度 O(n\omega^2)，其中 \omega\le 31 表示值域。

至于输出方案，把原先 DP 的 01 状态改为记录转移来的异或和即可，初始全部设为 -1，对于 sz_u 为偶数的情况，令 F(u,0,son_u)=-2 做特殊标记。

由于 \sum son_u 是 O(n) 的，直接开 DP 数组会 MLE，采用 $\texttt{std::vector}