g6-09075. 换根的两种代价 未做

给一棵以 $1$ 为根、共 $n$ 个结点的有根树。换根类问题有两种经典做法：

• 做法一（逐点换根）：把 $1,2,\dots ,n$ 每个点轮流当一次根。每换一个根，就从新的根出发，把整棵树完整遍历一遍。
• 做法二（两遍扫描）：固定以 $1$ 为根，只扫两遍：第一遍自底向上（后序）扫整棵树，第二遍自顶向下（前序）再扫整棵树。

一遍完整遍历，无论从哪个点出发，都会把树上的 $n$ 个点每个恰好进入一次。请你分别算出两种做法的总访问次数，输出这两个数。

树的形态不影响本题答案，但输入中仍然给出一棵具体的树，请照常读入。

第一行一个整数 $n$，表示结点数。

接下来 $n-1$ 行：第 $i$ 行一个整数 $f_i$（$2\le i\le n$），表示结点 $i$ 的父结点。

$n=1$ 时没有任何父结点行。

共两行：第一行输出做法一的总访问次数；第二行输出做法二的总访问次数。

• $1\le n\le 10^5$
• $1\le f_i<i$
• 注意：做法一的总访问次数最大可达 $10^{10}$，超出 32 位有符号整数的表示范围

访问次数：一次遍历过程中，每进入一个结点，就记一次访问。把整棵树完整扫一遍，无论树长什么样、从哪个点出发，都恰好访问 $n$ 次——因为每个点各被进入一次。

据此可以数账：做法一共要跑 $n$ 遍，总访问次数是 $n$ 个 $n$ 相加，即 $n\times n$；做法二只跑 $2$ 遍，总访问次数是 $2$ 个 $n$ 相加，即 $2\times n$。两份程序算出的换根答案完全相同，访问次数却差了约 $n$ 倍——把 $O(n^2)$ 与 $O(n)$ 换算成具体数字，正是估计程序会不会超时的第一步。

$n=1$ 时树上只有 $1$ 个点：做法一遍历 $1$ 遍共访问 $1$ 次，做法二要遍历 $2$ 遍共访问 $2$ 次。数据很小的时候遍数多的做法反而访问更多，这说明复杂度刻画的只是数据变大时的增长趋势。