Imbalance

题目信息

时间限制: 1s

空间限制: 256M

输入文件: imbalance.in

输出文件: imbalance.out

题目描述

上周 DB（Dream Bear） 做了均衡区间，但是它没过。

于是 DB 急了，就打算出一道 《非均衡区间》，但是求非均衡区间只要 $n^2 - ans$ （均衡区间数） 即可。

出了一个原题， DB 更急了，于是 DB 就打算做完全非均衡区间。DB 一下子就想出了完全非均衡区间的解法，并开始嘲讽你。

但是你比 DB 强多了，所以你不用做完全非均衡区间，你直接做完全非均衡路径，直接薄纱 DB。

如果树上一条简单路径满足：路径上点权最大值和最小值都在路径的端点上，并且路径的两个端点不相同；那么称之为完全非均衡路径。

给定一棵树，点权就是点的编号（是 $1$ 到 $n$ 的排列）。

求这颗树上的完全非均衡路径数量。

输入格式

第一行 $n$ 表示点数。

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

输出格式

一行一个整数表示答案。

样例

样例输入 1

3  
1 2
2 3

样例输出 1

3

其他样例见下发文件。

数据范围与提示

无捆绑测试。

对于所有数据，$1\le n\le 5\times 10^5$。