预处理 DFS 序?\operatorname{dfn}(i)dfn(i)?和每个节点的子树中 DFS 序最大值?\operatorname{low}(i)low(i)，将树上问题转化为序列问题。我们可以把「出现次数为奇数」转化为异或操作，考虑分块，在每个块内维护一个?bitset，每一个二进制位代表?[0,p)[0,p)?范围内的一个整数，维护块内异或和即可。

• 对于?11?操作，我们可以将?bitset?整体左移?vv?位，对于大于?pp?位的部分截断并移至最低位。
• 对于?22?操作，直接暴力重构整个块即可。
• 对于?33?操作，我们考虑此操作的性质。我们可以在预处理时按着节点的编号顺序从小到大进行 DFS 搜索，由于「每个点只能被执行?33?操作至多?11?次」，我们可以得出一个结论：每个点进行最多一次?33?操作后，所有节点的 DFS 序均不会变。而操作的点?ii?它的新的父亲节点的 low 值?\operatorname{low}(fa_i)low(fai?)?会变为?\max(\operatorname{low}(fa_i),\operatorname{low}(i))max(low(fai?),low(i))。我们可以对每个点开一个?set?来维护它的红色儿子的编号，对于每次?33?操作在?set?中完成删除数字和寻找前驱的操作。
• 对于?44?操作，首先求出所有整块区间?bitset?的异或和，在暴力异或上边角块。对于异或和从小到大数第?ii?位，若此位为?11，则将答案增加?i^kik?即可。

时间复杂度：1,2,41,2,4?操作均为每次?O(\dfrac{m\sqrt n}{w})O(wmn??)，33?操作每次?O(\log n)O(logn)。由于 std 使用的是手写?bitset，其常数为?w=128w=128，所以这题可能稍微有些卡常。

PS：据 lxl 说常数?w=128w=128?是假的，int128?内部实际还是用?long long?模拟，所以常数可能比用?unsigned long long?的还要慢。不过至少把?std::bitset?卡掉了。就当是增大 std 常数以放宽时间限制吧。