U576872 tree

日记今天学习了二叉搜索树。二叉搜索树上，对于一个节点，它的左子树上每个点的点权都小于它的点权，它的右子树上每个点的点权都大于它的点权。

日记很喜欢二叉搜索树，所以她想把这种性质扩展到一般的树上。 现有一棵以节点 $1$ 为根的树，她给树上每一个节点钦定了一个不同的点权 $w_i$。 她认为一对节点 $(u, v)$ 是好的，当且仅当 $w_u < w_{\operatorname{lca}(u, v)} < w_v$，其中 $\operatorname{lca}(u, v)$ 为 $u, v$ 的最近公共祖先。 现在，她想让这棵树尽可能的好，也就是让好的节点对数最多。 额外地，她认为排列是美观的，因此她要求点权 $w_i$ 构成一个 $1 \sim n$ 的排列。 请输出好的节点对数的最大值。

第 $1$ 行，$1$ 个正整数 $n$，代表树有 $n$ 个节点。 接下来 $(n-1)$ 行，每行 $2$ 个正整数 $u, v$，代表树上有一条连接 $(u, v)$ 的边。 保证输入构成一棵树。

输出 $1$ 行 $1$ 个非负整数，为好的节点对数的最大值。

本题设置 25 个测试点，每个测试点 4 分。每个测试点满足一些限制，见下： |$id$ |$n \leq$ |特殊性质 | | ------ | ------ | ------ | |$1$ |$10$ |$r$ | |$2$ |$10$ | | |$3$ |$5000$ |$r$ | |$4$ |$5000$ |$r$ | |$5$ |$5000$ | | |$6$ |$5000$ | | |$7$ |$5000$ | | |$8$ |$3 \times 10^4$ |$r$ | |$9$ |$3 \times 10^4$ |$r$ | |$10$ |$3 \times 10^4$ | | |$11$ |$3 \times 10^4$ | | |$12$ |$3 \times 10^4$ | | |$13$ |$10^6$ |$s(1)$ | |$14$ |$10^6$ |$s(1)$ | |$15$ |$10^6$ |$s(2)$ | |$16$ |$10^6$ |$s(2)$ | |$17$ |$10^6$ |$s(3)$ | |$18$ |$10^6$ |$s(3)$ | |$19$ |$10^6$ |$s(4)$ | |$20$ |$10^6$ |$s(4)$ | |$21$ |$10^6$ |$h(10)$ | |$22$ |$10^6$ |$h(10)$ | |$23$ |$10^6$ |$r$ | |$24$ |$10^6$ | | |$25$ |$10^6$ | | 特别地，特殊性质 `s(x)` 代表：对每个节点，其儿子节点个数不超过 $x$；`h(x)` 代表：若钦定根节点深度为 $1$，每个节点的深度为其父节点深度 $+1$，则节点的深度最大值不超过 $x$；`r` 代表：数据随机生成，即 $i$ 的父亲在 $[1, i-1]$ 中等概率随机选取。 对全部数据，有 $1 \leq n \leq 10^6$。