U648884 MX-BJ 树上均衡路径

MX 某场 NOIP 模拟赛 T4，搬过来，数据是自己随的，不保证强度。

如果树上一条简单路径满足：路径上点权最大值和最小值**都**在路径的端点上，并且**路径的两个端点不相同**；那么称之为完全非均衡路径。 给定一棵树，点权就是点的编号（是 $1$ 到 $n$ 的排列）。 求这颗树上的完全非均衡路径数量。

第一行 $n$ 表示点数。 接下来 $n - 1$ 行每行两个整数 $u,v$，表示一条树边 $(u,v)$。

一行一个整数表示答案。

由于 std 是补题代码，进行了卡常，测试了几种点分治基本都在 $1.5s$ 左右,于是开了 $2.5s$，原题是给了 $1s$ 的时限。 对于所有数据，$1 \leq n \leq 5 \times 10^5$。 | 数据占比 | $n$ | 特殊性质 | |----------|------------------|------------------------------| | 20% | $\leq 1000$ | 无 | | 15% | $\leq 10^5$ | 每个点的度数不超过 2 | | 15% | $\leq 10^5$ | 有一个度数为 $n - 1$ 的点 | | 20% | $\leq 10^5$ | 无 | | 30% | $\leq 5 \times 10^5$ | 无 | [题解](https://www.luogu.com.cn/article/i6eh6rei)