P17541 25HRS


Simons 在阳台上种植了一棵 $n$ 个点的有标号有根**无向**树，树的根为 $1$。点 $x$ 的父亲为 $f_x$。 Simons 可以对这棵树进行若干次 Cut。一次完整的 Cut 包含两个操作： - 选择两个点 $x,y$，使得 $f_x=f_y$ 且 $x\ne y$。 - 断开 $(x,f_x)$ 这条边，将 $x$ 连接到 $y$ 下方作为 $y$ 的儿子。即 $f_x\gets y$。 显然，在 Cut 之后，我们得到的仍然是一棵以 $1$ 为根的有标号有根树。 你的任务是，计算至少需要多少次 Cut 使得整棵树构成一条链，并计算有多少种本质不同的**最短** Cut 操作序列能达到使整棵树构成一条链的目的，对 $998244353$ 取模。 两种 Cut 操作序列本质不同当且仅当长度（即操作次数）不同或者存在某一次操作选择的**有序点对** $(x,y)$ 不同。 **在本题中，一棵大小为 $n$ 的无向树为一条链，当且仅当存在一条简单路径 $s\leadsto t$ 上的点数为 $n$。**

**本题包含多组测试。** 第一行包含一个整数 $T$，表示该测试点内的测试数据组数。 对于每组数据： 第一行一个整数 $n$ 表示树的节点数量。 接下来一行用空格隔开输入 $n-1$ 个整数 $f_2,f_3,\dots,f_n$，依次表示 $2$ 到 $n$ 号节点的父亲。保证 $f_i

共 $T$ 行。对于每组数据，一行两个整数，用空格隔开。 第一个整数表示最少的 Cut 次数使得整棵树构成一条链，第二个整数表示满足条件的本质不同的 Cut 操作序列数量对 $998244353$ 取模的值。

### 样例解释 #### 样例 #1 解释  Simons 有两种本质不同的 Cut 方式使得 Cut 次数最少，并且整棵树能变成一条链： - Cut $(6,5)$，这将导致 $6$ 和 $3$ 之间的边断开，$6$ 成为 $5$ 的儿子，之后整棵树成为一条链（$4\to 2\to 1\to 3\to 5\to 6$ 是一条满足链判定条件的路径）。 - Cut $(5,6)$，这将导致 $5$ 和 $3$ 之间的边断开，$5$ 成为 $6$ 的儿子，之后整棵树成为一条链（$4\to 2\to 1\to 3\to 6\to 5$ 是一条满足链判定条件的路径）。 ### 数据范围 **本题开启捆绑测试。** 对于 $100\%$ 的数据，$1\le T\le 10^4$，$2\le n,\sum n\le 5\times 10^5$。特别地，$f_i