1012. 今晚吃 TopTree

题目描述

题目背景和题意无关，可以跳过。

Rake 和 Compress 是两种重要的合并操作。考虑将一棵树每次将两条边进行 R/C 让树越来越小的过程，并根据此过程建立重构树，称这棵树为 Top Tree。

现在在 Top Tree 上取出所有极大的不超过 $B$ 的簇，就构成了一个合法 的 Top Cluster 分解。只不过这样的簇个数没有保证。

考虑按照全局平衡二叉树的方式构建。先将其改为二叉树：每个点向轻儿子连的边也按照子树大小带权平衡一下，然后每个点直接合并两个儿子簇即可。

Top Tree 能维护的范围是能用簇信息表出的范围。实际上，大多数树上范围都能如此表出。可以说 Top Tree 在几乎所有情况下都是最优分治结构。

但是全局平衡二叉树在结构上并不是最优的，在常数优化场景中，需要保证合并簇的总次数尽可能小。此时可以将它形式化为如下问题：

题目描述：给定一棵以顶点 $1$ 为根、包含 $n$ 个顶点的有根树。输入中的顶点称为原始顶点。根的深度为 $0$，其他顶点的深度为其到根的边数；树的高度为所有顶点深度的最大值。

你可以任意次执行以下操作：

• 选择当前树中的一个顶点 $u$ 及其两个不同的儿子 $v,w$；
• 新建一个顶点 $r$，令 $r$ 成为 $u$ 的儿子，并令 $v,w$ 改为 $r$ 的儿子。顶点 $v,w$ 原有的子树均保持不变。

你需要通过上述操作，使最终树中的每个顶点至多有两个儿子。

分别求出以下两个量的最小值：

• 最终树的高度；
• 所有 $n$ 个原始顶点在最终树中的深度之和。新建顶点的深度不计入这个和。

两个最小值互相独立，可以由两种不同的操作方案取得。

定义路径长度为边数，则深度为某顶点到根的路径长度，而高度为深度最大的顶点深度。

输入格式

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 10^6$）表示测试数据组数。

接下来对于每一组测试数据：

第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示原始顶点数。

接下来，如果 $n\ge 2$，那么在第二行输入 $n-1$ 个整数 $p_2,p_3,\cdots,p_n$（$1 \le p_i < i$），其中 $p_i$ 表示顶点 $i$ 的父亲。

数据保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每一组数据，输出包含一行两个整数，依次表示最终树的最小高度和原始顶点的最小深度和。

样例输入

3
1
4
1 1 1
13
1 2 2 3 3 4 4 1 9 10 11 1

样例输出

0 0
2 5
4 33

提示

在第二组数据中，根有三个儿子。将其中两个儿子放到同一个新建顶点下，可以得到高度 $2$；三个原始儿子的深度分别为 $1,2,2$，深度和为 $5$。

题目背景由白井黑子撰写。

来源：2026杭电多校-测试专用（南外） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1235&pid=1012