主要思路
先建好树，大概思考一下应该可以推导出：倍增找标记点，然后根到区间修改。然而正解也是这样写，只不过细节有点多，我在这里提一下：回答询问\(x\)时，先把他父亲提到根，然后找最近的点；找到了就把深度大的全部打标记反过来。
先建好树，大概思考一下应该可以推导出：倍增找标记点，然后根到区间修改。然而正解也是这样写，只不过细节有点多，我在这里提一下：回答询问\(x\)时，先把他父亲提到根，然后找最近的点；找到了就把深度大的全部打标记反过来。
这道题就是 DAG 求支配树裸题，过程是这样的：先做一遍拓扑排序，然后对于第\(i\)个点\(u\)而言，前\(i – 1\)个点已经完成，所以其支配树上的父亲就是入边起点的 LCA。稍稍处理一下即可。然后再在支配树上进行 DFS 求出每个子树的大小即可。
想了半天，最后一看是离线来维护，直接吐血。
首先大概能想到用本质不同的异或和与区间异或和进行异或得到答案。因为这样可以把出现次数为奇数次的给过滤掉并得到最终的答案。考虑如何得到本质不同的区间异或和，一种方式是使用主席树进行维护，另一种方式是进行离线维护。我们可以在树状数组中维护本质不同的前缀异或：我们把每个数往尽可能近的地方塞，这个时候就需要用 map 来判断要不要移动。