CF1856E2.PermuTree (hard version)

This is the hard version of the problem. The differences between the two versions are the constraint on $n$ and the time limit. You can make hacks only if both versions of the problem are solved.

You are given a tree with $n$ vertices rooted at vertex $1$.

For some permutation$^\dagger$ $a$ of length $n$, let $f(a)$ be the number of pairs of vertices $(u, v)$ such that $a_u \lt a_{\operatorname{lca}(u, v)} \lt a_v$. Here, $\operatorname{lca}(u,v)$ denotes the lowest common ancestor of vertices $u$ and $v$.

Find the maximum possible value of $f(a)$ over all permutations $a$ of length $n$.

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

这是该问题的困难版本。两个版本之间的区别在于对 $n$ 的约束以及时间限制。只有当该问题的两个版本均被解决时，你才可以进行 hack。

你被给定一棵以顶点 $1$ 为根、包含 $n$ 个顶点的树。

对于某个长度为 $n$ 的排列$^\dagger$ $a$，定义 $f(a)$ 为满足 $a_u \lt a_{\operatorname{lca}(u, v)} \lt a_v$ 的顶点对 $(u, v)$ 的数量。其中，$\operatorname{lca}(u,v)$ 表示顶点 $u$ 和 $v$ 的最近公共祖先。

求所有长度为 $n$ 的排列 $a$ 中，$f(a)$ 的最大可能值。

$^\dagger$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 中互不相同的 $n$ 个整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

The first line contains a single integer $n$ ($2 \le n \le 10^6$).

The second line contains $n - 1$ integers $p_2,p_3,\ldots,p_n$ ($1 \le p_i \lt i$) indicating that there is an edge between vertices $i$ and $p_i$.

第一行包含一个整数 $n$（$2 \le n \le 10^6$）。

第二行包含 $n - 1$ 个整数 $p_2, p_3, \ldots, p_n$（$1 \le p_i < i$），表示顶点 $i$ 与顶点 $p_i$ 之间存在一条边。

Output the maximum value of $f(a)$.

输出 $f(a)$ 的最大值。

The tree in the first test:

One possible optimal permutation $a$ is $[2, 1, 4, 5, 3]$ with $4$ suitable pairs of vertices:

• $(2, 3)$, since $\operatorname{lca}(2, 3) = 1$ and $1 \lt 2 \lt 4$,
• $(2, 4)$, since $\operatorname{lca}(2, 4) = 1$ and $1 \lt 2 \lt 5$,
• $(2, 5)$, since $\operatorname{lca}(2, 5) = 1$ and $1 \lt 2 \lt 3$,
• $(5, 4)$, since $\operatorname{lca}(5, 4) = 3$ and $3 \lt 4 \lt 5$.

The tree in the third test:

The tree in the fourth test:

第一个测试用例中的树：

一种可能的最优排列 $a$ 为 $[2, 1, 4, 5, 3]$，包含 $4$ 对满足条件的顶点：

• $(2, 3)$，因为 $\operatorname{lca}(2, 3) = 1$ 且 $1 \lt 2 \lt 4$，
• $(2, 4)$，因为 $\operatorname{lca}(2, 4) = 1$ 且 $1 \lt 2 \lt 5$，
• $(2, 5)$，因为 $\operatorname{lca}(2, 5) = 1$ 且 $1 \lt 2 \lt 3$，
• $(5, 4)$，因为 $\operatorname{lca}(5, 4) = 3$ 且 $3 \lt 4 \lt 5$。

第三个测试用例中的树：

第四个测试用例中的树：