AT_agc079_a.Tree Contraction Sequence
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There is a rooted tree with N vertices. The vertices are numbered 1,2,…,N, and the root is vertex 1. The parent of each vertex v (2≤v≤N) is vertex Pv, where 1≤Pv<v.
Additionally, each vertex holds an integer sequence. Initially, the sequence held by vertex v is (v).
You will perform the following operation N−1 times.
- Choose a vertex v with 2≤v≤N that has not been chosen in any previous operation, and let u be its parent in the current tree.
- Concatenate the sequence of vertex v to the end of the sequence of vertex u.
- Contract vertex v into its parent u. That is, delete vertex v and make all of its children into children of vertex u.
Find the number, modulo 998244353, of operation sequences such that the sequence of the remaining vertex 1 after all operations equals (1,2,…,N). Here, two operation sequences are considered different if their sequences of chosen vertices are different.
You are given T test cases; solve each of them.
有一棵包含 N 个顶点的有根树。顶点编号为 1,2,…,N,根节点为顶点 1。每个顶点 v(其中 2≤v≤N)的父节点为顶点 Pv,满足 1≤Pv<v。
此外,每个顶点持有一个整数序列。初始时,顶点 v 所持有的序列为 (v)。
你将执行以下操作共 N−1 次:
- 选择一个尚未在之前任何操作中被选过的顶点 v(其中 2≤v≤N),并令 u 为其在当前树中的父节点;
- 将顶点 v 所持有的序列拼接到顶点 u 所持有序列的末尾;
- 将顶点 v 收缩(contract)至其父节点 u:即删除顶点 v,并将 v 的所有子节点全部变为顶点 u 的子节点。
求满足如下条件的操作序列的个数(对 998244353 取模):在所有操作完成后,剩余的唯一顶点 1 所持有的序列恰好为 (1,2,…,N)。此处,若两个操作序列所选择的顶点序列不同,则认为它们是不同的操作序列。
你将收到 T 组测试用例,请对每组用例求解。
输入格式
The input is given from Standard Input in the following format:
T
case1
case2
⋮
caseT
Each test case is given in the following format:
N
P2 P3 … PN
输入从标准输入中按以下格式给出:
T
case1
case2
⋮
caseT
每个测试用例按以下格式给出:
N
P2 P3 … PN
输出格式
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,4, for example, the sequences change as follows.
- Choosing vertex 3 makes the sequence of vertex 2 equal to (2,3).
- Choosing vertex 2 makes the sequence of vertex 1 equal to (1,2,3).
- Choosing vertex 4 makes the sequence of vertex 1 equal to (1,2,3,4).
There are 2 orders of choosing vertices that satisfy the condition: (2,3,4) and (3,2,4).
Constraints
- 1≤T≤125000
- 2≤N≤250000
- 1≤Pv<v (2≤v≤N)
- The sum of N over all test cases in a single input is at most 250000.
- All input values are integers.
样例 1 解释:
在第一个测试用例中,若按顺序 3,2,4 选择顶点,则各序列的变化如下:
- 选择顶点 3 后,顶点 2 的序列为 (2,3);
- 选择顶点 2 后,顶点 1 的序列为 (1,2,3);
- 选择顶点 4 后,顶点 1 的序列为 (1,2,3,4)。
满足条件的顶点选择顺序共有 2 种:(2,3,4) 和 (3,2,4)。
约束条件
- 1≤T≤125000
- 2≤N≤250000
- 1≤Pv<v(其中 2≤v≤N)
- 单组输入中所有测试用例的 N 值之和不超过 250000;
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?