← 返回题目列表

AtCoder · abc329_g

G. 树上交货

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

分数: 625 点

问题陈述

给你一棵二叉树 N 顶点。顶点已编号 1 to N,带顶点 1 是根。的 i第边缘 (1\leq i \leq N-1) 连接顶点 i+1 和顶点 P_i\ (\leq i) 双向。

有一个篮子, M 这棵树上有球。球有编号 1 to M,以及每个球 j 有指定 起始顶点 S_j 和 目标顶点 T_j。最初,篮子是空的并放置在顶点 1,并且球被放置在它们各自的起始顶点。

您可以按任意顺序执行以下操作任意次数。

  • 让 v 是放置篮子的当前顶点。执行以下操作之一:
    • 选择连接到顶点的一条边 v,并将篮子沿着该边移动到相邻的顶点。篮子里的球也随之移动。
    • 选择一个具有起始顶点的球 v 仍放置在 v,并将其放入篮子中。仅当篮子中包含的物品少于 K 球(即篮子不能容纳 K+1 或更多球)。
    • 选择一个具有球门顶点的球 v 从篮子里拿出来,放在顶点 v.

操作序列称为 良好的操作顺序 当且仅当篮子最终为空并放置在顶点 1,球最终被放置在各自的球门顶点。

由于多次移动篮子很累,因此篮子的移动路径应该在返回顶点之前精确地遍历每条边两次 1。求模数 998244353,在那些路径中,使得沿着该路径存在良好的操作序列。

约束

  • 2\leq N \leq 10^4
  • 1\leq M \leq 2\times 10^5
  • 1\leq K \leq 10^3
  • 1\leq P_i \leq i
  • 对于每个 v\ (1\leq v \leq N),最多有两个 i是这样的 P_i=v.
  • 1\leq S_j, T_j \leq N
  • S_j \neq T_j
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M K
P_1 P_2 \dots P_{N-1}
S_1 T_1
S_2 T_2
\vdots
S_M T_M

输出

打印数字,模数 998244353,在返回顶点之前遍历每条边两次的路径 1 使得沿着该路径存在良好的操作序列。


示例输入 1

5 2 1
1 1 3 3
2 4
5 3

示例输出 1

1

给定的图表如下图所示。顶点旁边的圆圈和正方形分别代表球的起始顶点和目标顶点。

在返回顶点之前每条边都经过两次的路径中 1,只有一条路径可以在该路径之后存在良好的操作顺序,如下所示:

在这里,您可以构建以下良好的操作序列:

  1. 将篮子移动到顶点 2.
  2. 放球 1 入篮。
  3. 将篮子移动到顶点 1.
  4. 将篮子移动到顶点 3.
  5. 将篮子移动到顶点 4.
  6. 拿球 1 从篮子中取出并将其放置在顶点 4.
  7. 将篮子移动到顶点 3.
  8. 将篮子移动到顶点 5.
  9. 放球 2 入篮。
  10. 将篮子移动到顶点 3.
  11. 拿球 2 从篮子中取出并将其放置在顶点 3.
  12. 将篮子移动到顶点 1.

示例输入 2

5 2 2
1 1 3 3
2 4
5 3

示例输出 2

2

的值 K 增加了 来自示例输入 1 的 1 。除了上面所示的路径之外,这还允许您为以下路径构建良好的操作序列。


示例输入 3

15 4 2
1 2 1 4 2 3 4 7 3 7 5 9 11 8
14 12
5 4
13 15
5 12

示例输出 3

8