← 返回题目列表

AtCoder · jsc2024_final_e

E. 树和后边缘

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

配点 : 1000 点

問題文

1 减去 N 编号最多为 N 由顶点组成的有根树 有 T 。 根是顶点 1 ,顶点 i (2 \leq i \leq N) 的父级是顶点 P_i (P_i<i)。 该树的边是有向边,每条边都从父项指向子项。

你 T 至 该值是 M 添加书籍边缘并创建有向图 我创建了 G 。 添加的第 i 条边是顶点 A_i 到顶点 B_i 的路上。 在这里,A_i,B_i 保证满足以下条件。 顶点位于

  • 1 \leq B_i<A_i \leq N
  • T 顶点在 A_i 是顶点 是 B_i 的后代
  • T 顶点在 A_i 不是叶子

也可以添加多个相同的边。

你现在是 G 的顶点 从 1 开始,重复以下操作,直至停止。

  • 如果没有边从当前顶点出来,则停止。
  • 如果有从当前顶点出来的边,则其中一条 1 随机均匀地选择一条边并将其移动到该边所指向的顶点。

停止前预计移动的次数。 使用\pmod{P} 找到它。

然而,在这个问题中 P 的值不能作为输入给出。 相反,我们使用满足以下所有约束的模型。 您选择 P 并 请解决 P 的问题。

  • P 是质数 答案可以由
  • 998244353 \leq P < 2 \times 10^9
  • \pmod{P} 定义
期待値 \pmod{P} 的定义

可以证明期望的期望值始终是有理数。将该值转换为不可约分数 当表示为 \frac{P}{Q} 时,Q \neq 0 \pmod{P} ,这个值为 据说可以通过\pmod{P} 来定义,Q = 0 \pmod{P} 据说是无法定义的。如果可以定义该值,R \times Q \equiv P \pmod{P}, 0 \leq R < P 的整数 选择 R 是唯一确定的。这个 请回答 R 。

关于本期的法官

法官将首先选择您的选择。 P 是第一个 2 检查是否满足两个条件。 如果不满足条件,则判定测试用例不正确。 如果满足条件,法官将 运行程序来解决 P 的问题。 法官回答 如果您可以计算\pmod{P} 的值,请将其与您的输出进行比较以确定其正确还是错误。 法官回答 我无法计算\pmod{P} ,但答案是 如果可以确定不能使用\pmod{P} 进行定义,则确定该测试用例不正确。 法官回答\pmod{P} 无法计算,答案是 如果无法确定是否可以通过\pmod{P} 定义,则判定测试用例正确。 注意,在这个问题的约束下,第一个 2 满足以下条件 P 出 99.9可以证明期望值可以定义为大于%并且法官可以正确计算它。

制約

  • 2 \leq N \leq 250000
  • 0 \leq M \leq 250000
  • 1 \leq P_i < i
  • 1 \leq B_i<A_i \leq N
  • T 顶点在 A_i 是顶点 是 B_i 的后代
  • T 顶点在 A_i 不是叶子
  • 所有输入值均为整数
  • 样本以外的测试用例是 50 或更少。

入力

输入是按以下格式从标准输入给出的。

N M
P_2 P_3 \cdots P_N
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

按以下格式输出您的答案。

ans P

这里 P 是您选择的质数, 这是ans 是 您也可以写\pmod{P} 中的答案。


入力例 1

3 0
1 2

出力例 1

2 998244353

入力例 2

3 1
1 2
2 1

出力例 2

4 998244353

入力例 3

7 5
1 2 2 4 4 3
3 1
2 1
3 2
4 2
3 2

出力例 3

453747441 998244353

入力例 4

20 25
1 2 3 2 5 2 6 1 9 2 2 12 13 1 2 16 17 16 19
13 12
12 1
17 1
6 5
5 1
13 12
12 2
17 16
17 16
17 16
19 16
6 5
16 2
6 5
9 1
9 1
13 12
13 12
6 5
19 16
6 5
17 16
6 5
13 1
13 12

出力例 4

529789893 998244353