← 返回题目列表

AtCoder · abc454_g

G. 子树中的模式

中文机器翻译题面 查看原题

分数: 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)