子树中的众数

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定一棵有 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$。顶点 $1$ 是根，顶点 $i$ 的父亲是顶点 $p_i$，并且 $p_i<i$。

每个顶点都有一种颜色：顶点 $i$ 的颜色为 $c_i$，其中 $1\le c_i\le N$。

对于每个 $v=1,2,\ldots,N$，完成下面的问题：

令 $f_i$ 表示以顶点 $v$ 为根的子树中，颜色为 $i$ 的顶点个数。求：

• 序列 $(f_1,f_2,\ldots,f_N)$ 中的最大值 $m$；
• 满足 $f_i=m$ 的、不超过 $N$ 的正整数 $i$ 的个数 $k$。

本题采用特殊的输入输出格式。

标准输入给出整数 $N$，以及整数 $\mathrm{seed},M,F$、$q_2,q_3,\ldots,q_M$ 和 $d_1,d_2,\ldots,d_M$。按以下过程还原 $p_2,p_3,\ldots,p_N$ 和 $c_1,c_2,\ldots,c_N$。

首先令 $\mathrm{state}=\mathrm{seed}$。依次处理 $i=2,3,\ldots,N$：

• 若 $i\le M$，令 $p_i=q_i$；
• 否则，令 $p_i=(\mathrm{state}\bmod(i-1))+1$，然后令 $\mathrm{state}=(\mathrm{state}\times1103515245+12345)\bmod 2^{31}$。

接着依次处理 $i=1,2,\ldots,N$：

• 若 $i\le M$，令 $c_i=d_i$；
• 否则，令 $c_i=(\mathrm{state}\bmod F)+1$，然后令 $\mathrm{state}=(\mathrm{state}\times1103515245+12345)\bmod 2^{31}$。

这里 $2^{31}=2147483648$。$\mathrm{state}$ 是变量，计算它时需要使用 64 位整数类型。

令 $m_i,k_i$ 分别表示对 $v=i$ 求得的 $m,k$。输出

$$\left(\sum_{i=1}^{N}(m_i\mathbin\oplus i)\times(k_i\mathbin\oplus i)\right)\bmod998244353,$$

其中 $\oplus$ 表示按位异或。计算时请注意溢出。

输入格式

第一行输入四个整数：

$$N\quad \mathrm{seed}\quad M\quad F$$

第二行输入 $M-1$ 个整数：

$$q_2\quad q_3\quad \cdots\quad q_M$$

第三行输入 $M$ 个整数：

$$d_1\quad d_2\quad \cdots\quad d_M$$

输出格式

输出一个整数，表示

$$\left(\sum_{i=1}^{N}(m_i\mathbin\oplus i)\times(k_i\mathbin\oplus i)\right)\bmod998244353.$$

样例输入 1

4 454 4 2
1 2 2
1 2 2 3

样例输出 1

29

样例解释 1

对于 $i=1$，有 $m_1=2,k_1=1$，对应贡献为 $0$。

对于 $i=2$，有 $m_2=2,k_2=1$，对应贡献为 $0$。

对于 $i=3$，有 $m_3=1,k_3=1$，对应贡献为 $4$。

对于 $i=4$，有 $m_4=1,k_4=1$，对应贡献为 $25$。

因此输出 $0+0+4+25=29$。

样例输入 2

6 123 2 2
1
1 2

样例输出 2

101

样例解释 2

本样例还原出的序列为

$$(p_2,p_3,\ldots,p_6)=(1,2,1,2,3),$$ $$(c_1,c_2,\ldots,c_6)=(1,2,2,1,2,1).$$

样例输入 3

15 1 4 5
1 2 3
5 3 1 3

样例输出 3

1199

样例解释 3

本样例还原出的序列为

$$(p_2,p_3,\ldots,p_{15})=(1,2,3,2,1,4,7,6,5,10,1,10,2,8),$$$$(c_1,c_2,\ldots,c_{15})=(5,3,1,3,4,2,2,2,4,2,2,5,3,5,3).$$

数据范围

• $2\le N\le2.5\times10^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$；
• 所有输入值均为整数。

根顶点的深度定义为 $0$。

子任务编号	分值	特殊限制
1	30	还原出的树中，每个顶点的深度均不超过 $2$
2		还原出的颜色序列中，不同颜色的个数不超过 $8$
3	40	无特殊限制