AT_abc454_g [ABC454G] Mode in the Subtree

给定一棵 $N$ 个点的树，以 $1$ 为根，节点 $i$ 的父亲为 $p_i$，颜色为 $c_i$。对于每个节点 $i$ 求其子树中的众数出现次数 $m_i$，以及众数的种类数 $k_i$。 **本题使用特殊的输入输出格式**。对于输入，读入 $N,\mathrm{seed},M,F,q_2 \sim q_M,d_1 \sim d_M$ 后，用以下伪代码生成 $p_2\sim p_N,c_1\sim c_N$，其中 `2^31` 表示 $2^{31}$： ```plain state = seed for i=2 to N: if i

第一行四个整数 $N,\mathrm{seed},M,F$。 第二行 $M-1$ 个整数 $q_2 \sim q_M$。 第三行 $M$ 个整数 $d_1 \sim d_M$。

一行，上面提到的答案。

### 数据范围 - $2 \le N \le 2.5 \times 10^6$ - $1 \le p_i < i$ - $1 \le c_i \le N$ - $1 \le \mathrm{seed} < 2^{31}$ - $2 \le M \le \min(N, 10^5)$ - $1 \le F \le N$ - $1 \le q_i < i$ - $1 \le d_i \le N$ - 所有输入值均为整数。 ### 样例解释 1 - $i=1$：$m_1=2, k_1=1, (m_1 \oplus 1) \times (k_1 \oplus 1) = 0$ - $i=2$：$m_2=2, k_2=1, (m_2 \oplus 2) \times (k_2 \oplus 2) = 0$ - $i=3$：$m_3=1, k_3=1, (m_3 \oplus 3) \times (k_3 \oplus 3) = 4$ - $i=4$：$m_4=1, k_4=1, (m_4 \oplus 4) \times (k_4 \oplus 4) = 25$ 输出 $0+0+4+25=29$。 ### 样例解释 2 这组测试数据中： - $p = (1, 2, 1, 2, 3)$ - $c = (1, 2, 2, 1, 2, 1)$ ### 样例解释 3 这组测试数据中： - $p = (1, 2, 3, 2, 1, 4, 7, 6, 5, 10, 1, 10, 2, 8)$ - $c = (5, 3, 1, 3, 4, 2, 2, 2, 4, 2, 2, 5, 3, 5, 3)$