#P17541. 25HRS
25HRS
背景
题目描述
Simons 在阳台上种植了一棵 个点的有标号有根无向树,树的根为 。点 的父亲为 。
Simons 可以对这棵树进行若干次 Cut。一次完整的 Cut 包含两个操作:
- 选择两个点 ,使得 且 。
- 断开 这条边,将 连接到 下方作为 的儿子。即 。
显然,在 Cut 之后,我们得到的仍然是一棵以 为根的有标号有根树。
你的任务是,计算至少需要多少次 Cut 使得整棵树构成一条链,并计算有多少种本质不同的最短 Cut 操作序列能达到使整棵树构成一条链的目的,对 取模。
两种 Cut 操作序列本质不同当且仅当长度(即操作次数)不同或者存在某一次操作选择的有序点对 不同。
在本题中,一棵大小为 的无向树为一条链,当且仅当存在一条简单路径 上的点数为 。
输入格式
本题包含多组测试。
第一行包含一个整数 ,表示该测试点内的测试数据组数。
对于每组数据:
第一行一个整数 表示树的节点数量。
接下来一行用空格隔开输入 个整数 ,依次表示 到 号节点的父亲。保证 。
输出格式
共 行。对于每组数据,一行两个整数,用空格隔开。
第一个整数表示最少的 Cut 次数使得整棵树构成一条链,第二个整数表示满足条件的本质不同的 Cut 操作序列数量对 取模的值。
1
6
1 1 2 3 3
1 2
5
6
1 2 2 3 3
9
1 2 2 3 1 4 2 3
12
1 1 3 1 1 1 7 6 1 7 6
14
1 1 1 4 5 2 4 1 7 5 3 4 13
28
1 1 3 1 1 1 3 5 7 1 5 5 13 8 9 5 15 6 5 12 6 22 12 9 11 1 9
2 4
4 32
7 268800
7 13440
20 872653206
提示
样例解释
样例 #1 解释

Simons 有两种本质不同的 Cut 方式使得 Cut 次数最少,并且整棵树能变成一条链:
- Cut ,这将导致 和 之间的边断开, 成为 的儿子,之后整棵树成为一条链( 是一条满足链判定条件的路径)。
- Cut ,这将导致 和 之间的边断开, 成为 的儿子,之后整棵树成为一条链( 是一条满足链判定条件的路径)。
数据范围
本题开启捆绑测试。
对于 的数据,,。特别地,。
| 子任务 | 特殊性质 | 得分 | |
|---|---|---|---|
| 1 | 无 | ||
| 2 | ^ | ||
| 3 | |||
| 4 | |||
| 5 | A | ||
| 6 | B | ||
| 7 | C | ^ | |
| 8 | 无 |
特殊性质 A:保证整棵树是一条以 为头的毛毛虫。
特殊性质 B: 有且仅有一个儿子。
特殊性质 C: 有不少于两个儿子。
:该性质的充要条件是,存在一条以 为根的链 使得所有点到这条链的距离为 或 。
后记

:::epigraph[——《25HRS》]
趁月色没殆尽 just try yeah
Kick snare and hi-hat
:::