AT_agc079_a.Tree Contraction Sequence

省选/NOI-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There is a rooted tree with NN vertices. The vertices are numbered 1,2,…,N1,2,\ldots,N, and the root is vertex 11. The parent of each vertex vv (2≤v≤N)(2 \leq v \leq N) is vertex PvP_v, where 1≤Pv<v1 \leq P_v < v.

Additionally, each vertex holds an integer sequence. Initially, the sequence held by vertex vv is (v)(v).

You will perform the following operation N−1N-1 times.

  • Choose a vertex vv with 2≤v≤N2 \leq v \leq N that has not been chosen in any previous operation, and let uu be its parent in the current tree.
  • Concatenate the sequence of vertex vv to the end of the sequence of vertex uu.
  • Contract vertex vv into its parent uu. That is, delete vertex vv and make all of its children into children of vertex uu.

Find the number, modulo 998244353998244353, of operation sequences such that the sequence of the remaining vertex 11 after all operations equals (1,2,…,N)(1,2,\ldots,N). Here, two operation sequences are considered different if their sequences of chosen vertices are different.

You are given TT test cases; solve each of them.

有一棵包含 NN 个顶点的有根树。顶点编号为 1,2,…,N1,2,\ldots,N,根节点为顶点 11。每个顶点 vv(其中 2≤v≤N2 \leq v \leq N)的父节点为顶点 PvP_v,满足 1≤Pv<v1 \leq P_v < v。

此外,每个顶点持有一个整数序列。初始时,顶点 vv 所持有的序列为 (v)(v)。

你将执行以下操作共 N−1N-1 次:

  • 选择一个尚未在之前任何操作中被选过的顶点 vv(其中 2≤v≤N2 \leq v \leq N),并令 uu 为其在当前树中的父节点;
  • 将顶点 vv 所持有的序列拼接到顶点 uu 所持有序列的末尾;
  • 将顶点 vv 收缩(contract)至其父节点 uu:即删除顶点 vv,并将 vv 的所有子节点全部变为顶点 uu 的子节点。

求满足如下条件的操作序列的个数(对 998244353998244353 取模):在所有操作完成后,剩余的唯一顶点 11 所持有的序列恰好为 (1,2,…,N)(1,2,\ldots,N)。此处,若两个操作序列所选择的顶点序列不同,则认为它们是不同的操作序列。

你将收到 TT 组测试用例,请对每组用例求解。

输入格式

The input is given from Standard Input in the following format:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

Each test case is given in the following format:

NN
P2P_2 P3P_3 …\ldots PNP_N

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

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

每个测试用例按以下格式给出:

NN
P2P_2 P3P_3 …\ldots PNP_N

输出格式

For each test case, output the answer.

对于每个测试用例,输出答案。

输入输出样例

  • 输入#1

    6
    4
    1 2 1
    5
    1 1 3 3
    2
    1
    5
    1 2 3 4
    4
    1 1 1
    8
    1 1 2 4 2 6 3

    输出#1

    2
    6
    1
    24
    1
    24

说明/提示

Sample 1 Explanation:
In the first test case, if the vertices are chosen in the order 3,2,43,2,4, for example, the sequences change as follows.

  • Choosing vertex 33 makes the sequence of vertex 22 equal to (2,3)(2,3).
  • Choosing vertex 22 makes the sequence of vertex 11 equal to (1,2,3)(1,2,3).
  • Choosing vertex 44 makes the sequence of vertex 11 equal to (1,2,3,4)(1,2,3,4).

There are 22 orders of choosing vertices that satisfy the condition: (2,3,4)(2,3,4) and (3,2,4)(3,2,4).

Constraints

  • 1≤T≤1250001 \leq T \leq 125000
  • 2≤N≤2500002 \leq N \leq 250000
  • 1≤Pv<v1 \leq P_v < v (2≤v≤N)(2 \leq v \leq N)
  • The sum of NN over all test cases in a single input is at most 250000250000.
  • All input values are integers.

样例 1 解释:
在第一个测试用例中,若按顺序 3,2,43,2,4 选择顶点,则各序列的变化如下:

  • 选择顶点 33 后,顶点 22 的序列为 (2,3)(2,3);
  • 选择顶点 22 后,顶点 11 的序列为 (1,2,3)(1,2,3);
  • 选择顶点 44 后,顶点 11 的序列为 (1,2,3,4)(1,2,3,4)。

满足条件的顶点选择顺序共有 22 种:(2,3,4)(2,3,4) 和 (3,2,4)(3,2,4)。

约束条件

  • 1≤T≤1250001 \leq T \leq 125000
  • 2≤N≤2500002 \leq N \leq 250000
  • 1≤Pv<v1 \leq P_v < v(其中 2≤v≤N2 \leq v \leq N)
  • 单组输入中所有测试用例的 NN 值之和不超过 250000250000;
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页