← 返回题目列表

Codeforces · 2081/E

E. 量词

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

给定一棵有根树,其中 $$$n+1$$$ 节点标记为从 $$$0$$$ 到 $$$n$$$,其中根是节点 $$$0$$$,并且 它唯一的子节点是节点 $$$1$$$。有$$$m$$$ 不同 芯片标记为从 $$$1$$$ 到 $$$m$$$,每个颜色为黑色或白色。最初,它们按照标签升序从上到下排列在边缘 $$$(0,1)$$$ 上。

筹码的初始位置。树节点以蓝色显示。

您可以按任意顺序执行以下操作任意次数(可能为零):

  • 选择两条边 ($$$u,v$$$) 和 ($$$v,w$$$),使得 $$$u$$$ 是 $$$v$$$ 的父级,$$$v$$$ 是 $$$w$$$ 的父级,其中边 ($$$u,v$$$) 至少包含一个码片。移动 最底部 边缘芯片 ($$$u,v$$$) 到 最上面 放置在边缘 ($$$v,w$$$),i。 即,首先是 ($$$v,w$$$) 上的所有现有筹码。
  • 选择两条边 ($$$u,v$$$) 和 ($$$v,w$$$),使得 $$$u$$$ 是 $$$v$$$ 的父级,$$$v$$$ 是 $$$w$$$ 的父级,其中边 ($$$v,w$$$) 至少包含一个码片。移动 最上面 边缘芯片 ($$$v,w$$$) 到 最底部 放置在边缘 ($$$u,v$$$),i。 即,位于 ($$$u,v$$$) 上所有现有筹码下方。
  • 选择两个 相邻 相同颜色的筹码位于同一边缘,并交换位置。
允许的操作。

每个芯片 $$$i$$$ 都有一个移动范围,定义为从根到节点 $$$d_i$$$ 的简单路径上的所有边。操作过程中,必须保证切屑不会移动到其移动范围之外的边缘。

最后,您必须将所有筹码移回边缘 $$$(0,1)$$$。可以发现芯片的顺序可能会改变。计算边缘 $$$(0,1)$$$ 对 $$$998\,244\,353$$$ 取模后最终排列的码片的可能排列数。

码片排列定义为长度为 $$$m$$$ 的序列,其中包含 标签 芯片从上到下。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5000$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 5000$$$) - 树的大小减一(即,树有 $$$n+1$$$ 节点)和芯片数。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \lt i$$$) - 从 $$$1$$$ 到 $$$n$$$ 的节点的父节点。当且仅当 $$$i = 1$$$(根的唯一子节点是节点 $$$1$$$)时,保证 $$$p_i = 0$$$。

第三行包含 $$$m$$$ 整数 $$$c_1, c_2, \ldots, c_m$$$ ($$$c_i \in \{0, 1\}$$$) — 每个芯片的颜色($$$0$$$ 为黑色,$$$1$$$ 为白色)。

第四行包含 $$$m$$$ 整数 $$$d_1, d_2, \ldots, d_m$$$ ($$$1\le d_i \le n$$$) — 每个筹码的移动范围。

保证所有测试用例中 $$$n$$$ 的总和不超过 $$$5000$$$,并且 $$$m$$$ 的总和不超过 $$$5000$$$。

输出

对于每个测试用例,输出一个整数 - 芯片的可能排列数以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

4
3 2
0 1 1
0 1
2 3
4 4
0 1 1 2
0 0 1 1
1 2 3 3
6 6
0 1 1 1 4 5
0 0 0 0 1 1
5 6 1 2 4 3
16 15
0 1 1 3 1 3 4 3 3 7 1 6 11 5 8 10
1 0 1 1 0 1 1 1 1 0 1 1 0 0 0
12 14 13 10 9 16 11 14 13 15 16 10 2 2 5

输出
复制

2
8
108
328459046

注意

在第一个测试用例中,我们可以达到以下 $$$2$$$ 排列:($$$1,2$$$) 和 ($$$2,1$$$)。

在第二个测试用例中,我们可以达到以下 $$$8$$$ 排列: ($$$1,2,3,4$$$), ($$$1,2,4,3$$$), ($$$1,3,2,4$$$), ($$$1,3,4,2$$$), ($$$1,4,2,3$$$), ($$$1,4,3,2$$$)、($$$2,1,3,4$$$) 和 ($$$2,1,4,3$$$)。