P14135 【MX-X22-T6】「TPOI-4F」Miserable EXperience

安慰一个伤心的人，真的好困难呢…… 在好友最需要自己的时候，明明有很多话可说，却只会“好惨”“拍拍”“抱抱”什么的，真的很让人自责啊。 如果萝卜能让所有人对感情认真起来，像她这样被伤害的人，是不是就会少一些呢？

小 C 被分手了，这让小 C 联想起了许多不高兴的事，她现在很伤心。而小萝卜正在试图让她的心重归平静。 现在有 $n$ 个事件困扰着小 C。根据小 C 的联想过程，这些事件可以看做一棵根为 $1$ 的外向树，其中边 $(u,v)$ 表示 $v$ 是由 $u$ 联想产生的，而点 $1$ 到点 $u$ 的距离称作 $u$ 的联想距离。同时每件事 $u$ 都有一个难过程度 $a_u$。 小萝卜每次可以进行两种操作其一： - 安慰小 C：选择一个事件并将其子树内所有事件的难过程度 $-1$。 - 抱抱小 C：选择一个数 $x$ 并将所有联想距离为 $x$ 的点的难过程度 $-1$。 对于每个点 $u$，设 $ans_u$ 表示使 $u$ 子树内的所有事件的难过程度都**恰好**为 $0$ 的最少操作数（$u$ 子树外的事件**没有限制**），无解则 $ans_u=-1$。小萝卜需要对所有 $i$ 求出 $ans_i$。其中各询问独立。 特别地，为防止输出量过多，只需要输出所有 $ans_i+1$ 的异或和即可。保证做法与此部分无关。 由于小 C 快要破防了，小萝卜只有 0.5 s 的时间。

由于输入量过大，本题输入文件经过了压缩。你可以通过以下代码来获取树上每个节点 $u$ 的父亲 $p_u$ 与点权 $a_u$： ```cpp const int MAXN = 1e6 + 10; int n, p[MAXN], a[MAXN]; char buf[1

输出一行，一个整数，表示 $\bigoplus^n_{i=1}(ans_i+1)$ 的值。

**【样例解释 #1】** 样例 $1$ 解密后的输入如下： ``` 5 1 1 2 2 3 9 5 10 10 ``` 对于 $u=1$，其中一种最优的操作方案如下： - 选择事件 $1$ 安慰小 C $3$ 次。之后 $a$ 为 $\{0,6,2,7,7\}$。 - 选择事件 $2$ 安慰小 C $6$ 次。之后 $a$ 为 $\{0,0,2,1,1\}$。 - 选择事件 $3$ 安慰小 C $2$ 次。之后 $a$ 为 $\{0,0,0,1,1\}$。 - 选择联想深度 $2$ 抱抱小 C $1$ 次。之后 $a$ 为 $\{0,0,0,0,0\}$。 需要 $12$ 次操作。可以证明并不存在更优的操作方案。对于事件 $u=1\sim 5$，$ans_u$ 分别为 $12,10,5,10,10$，$ans_u+1$ 的异或和为 $0$，故输出 $0$。 **【数据范围】** **本题采用捆绑测试。** |子任务编号|$n\le$|$a_i\le$|特殊性质|分值| |:-:|:-:|:-:|:-:|:-:| |$1$|$5$|$10$|无|$5$| |$2$|$100$|$100$|^|$12$| |$3$|$10^3$|$10^9$|AB|$6$| |$4$|^|^|A|$8$| |$5$|^|^|B|$9$| |$6$|^|^|无|$12$| |$7$|$2\times10^5$|^|B|$13$| |$8$|^|^|无|$14$| |$9$|$10^6$|^|^|$21$| - 特殊性质 A：对于任意 $2 \le u \le n$，保证 $p_u=u-1$。 - 特殊性质 B：对于任意 $2 \le u \le n$，保证 $a_u\ge a_{p_u}$。 对于所有数据，保证 $1\le n\le 10^6$，$0\le a_i\le 10^9$，$1\le p_i