33OJ
登录 注册

#P17541. 25HRS

    ID: 20166 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>贪心洛谷原创O2优化树论排列组合前缀和洛谷月赛Ad-hoc

25HRS

背景

题目描述

Simons 在阳台上种植了一棵 nn 个点的有标号有根无向树,树的根为 11。点 xx 的父亲为 fxf_x。

Simons 可以对这棵树进行若干次 Cut。一次完整的 Cut 包含两个操作:

  • 选择两个点 x,yx,y,使得 fx=fyf_x=f_y 且 x≠yx\ne y。
  • 断开 (x,fx)(x,f_x) 这条边,将 xx 连接到 yy 下方作为 yy 的儿子。即 fx←yf_x\gets y。

显然,在 Cut 之后,我们得到的仍然是一棵以 11 为根的有标号有根树。

你的任务是,计算至少需要多少次 Cut 使得整棵树构成一条链,并计算有多少种本质不同的最短 Cut 操作序列能达到使整棵树构成一条链的目的,对 998244353998244353 取模。

两种 Cut 操作序列本质不同当且仅当长度(即操作次数)不同或者存在某一次操作选择的有序点对 (x,y)(x,y) 不同。

在本题中,一棵大小为 nn 的无向树为一条链,当且仅当存在一条简单路径 s⇝ts\leadsto t 上的点数为 nn。

输入格式

本题包含多组测试。

第一行包含一个整数 TT,表示该测试点内的测试数据组数。

对于每组数据:

第一行一个整数 nn 表示树的节点数量。

接下来一行用空格隔开输入 n−1n-1 个整数 f2,f3,…,fnf_2,f_3,\dots,f_n,依次表示 22 到 nn 号节点的父亲。保证 fi<if_i<i。

输出格式

共 TT 行。对于每组数据,一行两个整数,用空格隔开。

第一个整数表示最少的 Cut 次数使得整棵树构成一条链,第二个整数表示满足条件的本质不同的 Cut 操作序列数量对 998244353998244353 取模的值。

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 (6,5)(6,5),这将导致 66 和 33 之间的边断开,66 成为 55 的儿子,之后整棵树成为一条链(4→2→1→3→5→64\to 2\to 1\to 3\to 5\to 6 是一条满足链判定条件的路径)。
  • Cut (5,6)(5,6),这将导致 55 和 33 之间的边断开,55 成为 66 的儿子,之后整棵树成为一条链(4→2→1→3→6→54\to 2\to 1\to 3\to 6\to 5 是一条满足链判定条件的路径)。

数据范围

本题开启捆绑测试。

对于 100%100\% 的数据,1≤T≤1041\le T\le 10^4,2≤n,∑n≤5×1052\le n,\sum n\le 5\times 10^5。特别地,fi<if_i<i。

子任务 ∑n≤\sum n\le 特殊性质 得分
1 88 无 1515
2 100100 ^
3 500500
4 10410^4
5 2×1052\times 10^5 A 55
6 B 1010
7 C ^
8 5×1055\times 10^5 无 1515

特殊性质 A:保证整棵树是一条以 11 为头的毛毛虫†^\dag。

特殊性质 B:11 有且仅有一个儿子。

特殊性质 C:11 有不少于两个儿子。

†^\dag:该性质的充要条件是,存在一条以 11 为根的链 1⇝s1\leadsto s 使得所有点到这条链的距离为 00 或 11。

后记

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