分数: 625 点
问题陈述
你得到了一棵有根的树 N 顶点编号 1 通过 N。顶点 1 是根,也是顶点的父级 i 是顶点 p_i (p_i \lt i).
每个顶点都有颜色:顶点 i 是用颜色着色的 c_i (1 \leq c_i \leq N).
对于每个 v = 1, 2, \dots, N,解决以下问题:
让 f_i 是用颜色着色的顶点数 i 以顶点为根的子树中的顶点之间 v.
查找:
- 最大值 m 序列中的值 (f_1, f_2, \dots, f_N),和
- 数量 k 正整数 i 不大于 N 这样 f_i = m.
输入/输出格式
此问题的输入和输出遵循特殊格式。
输入格式
从标准输入中,您将获得整数 N 以及整数 \mathrm{seed}, M, F 和 q_2, q_3, \dots, q_M, d_1, d_2, \dots, d_M。重建 p_2, p_3, \dots, p_N 和 c_1, c_2, \dots, c_N 使用以下伪代码描述的计算。 (这里, 2^31 意味着 2^{31}=2147483648。请注意 \mathrm{state} 是一个变量,并且 64- 计算需要位整数类型 \mathrm{state}.)
state = seed
for i=2 to N:
if i <= M:
p[i] = q[i]
else:
p[i] = (state mod (i-1)) + 1
state = (state * 1103515245 + 12345) mod 2^31
for i=1 to N:
if i <= M:
c[i] = d[i]
else:
c[i] = (state mod F) + 1
state = (state * 1103515245 + 12345) mod 2^31
输出格式
让 m_i 和 k_i 表示 分别是 m 和 k 当 v=i。输出这个值:
\left(\displaystyle \sum_{i=1}^N (m_i \oplus i)\times (k_i \oplus i)\right) \bmod 998244353
在这里, \oplus 表示按位异或。注意计算过程中的溢出。
约束
- 2 \leq N \leq 2.5 \times 10^6
- 1 \leq p_i \lt i
- 1 \leq c_i \leq N
- 1 \leq \mathrm{seed} \lt 2^{31}
- 2 \leq M \leq \min(N, 10^5)
- 1 \leq F \leq N
- 1 \leq q_i \lt i
- 1 \leq d_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N \mathrm{seed} M F
q_2 q_3 \dots q_M
d_1 d_2 \dots d_M
输出
输出 \left(\displaystyle \sum_{i=1}^N (m_i \oplus i)\times (k_i \oplus i)\right) \bmod 998244353.
示例输入 1
4 454 4 2 1 2 2 1 2 2 3
示例输出 1
29
- 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
6 123 2 2 1 1 2
示例输出 2
101
的值 p_i, c_i 本次测试用例如下:
- p = (1, 2, 1, 2, 3)
- c = (1, 2, 2, 1, 2, 1)
示例输入 3
15 1 4 5 1 2 3 5 3 1 3
示例输出 3
1199
的值 p_i, c_i 本次测试用例如下:
- 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)