算法一

按提意模拟。

发现数据随机情况下的时间复杂度是 $O(n + m)$ 的，故有 $30$ 分。

算法二

菊花图的部分分随便乱搞一下就行了，可以得到 $10$ 分。

算法三

发现某个点的儿子对应 BFS 序连续的一段。如果修改全在询问前面，直接差分即可。期望得分 $10$ 分。

算法四

用线段树维护算法三，时间复杂度 $O(m \log n)$，可以勉强通过本题。

算法五

记两个数组 $A, B$。我们暴力改自己和父亲的 $A$，儿子的修改记在自己的 $B$ 上。这样一个点的权值就是 $A[x]\text{ xor }B[\text{fa}(x)]$，如果询问随机，那么直接暴力查每个点加起来就行了。可以通过 $70$ 分的数据。

算法六

额外地维护一下儿子 $A$ 的和，询问时就可以暴力查父亲和自己，直接查儿子了。时间复杂度 $O(n + m)$，可以通过本题。

吐槽

感觉这题的正解还挺好想的，并且十分好写：它甚至不需要建图。

可是为什么大家写了线段树呢 QAQ