1951 - 小明喜欢树 V2
Description
小明非常喜欢树，有一天小明得到这样一棵树，每个树节点都有一个编号，有 n 个节点的树的编号为 1 到 n ，每个编号代表该节点的海拔高度。
现在小明要在这颗树上找到一些路径，从起点到终点需要满足海拔先单调上升后单调下降的性质，起点或终点不同即为不同的路径，问满足条件的路径有多少条，聪明的你可以帮助小明解决这个问题吗？
Input
第一行输入一个整数 n
接下来 n-1 行，每行有两个整数，表示这两个节点连在一起
Output
输出路径的个数。
Examples
Input
5 1 5 4 5 2 4 3 4
Output
8
Hint
对于 10% 的数据，1\leq n \leq 8
对于 50% 的数据，1\leq n \leq 1024
对于 100% 的数据，1\leq n \leq 3 \times 10^5
样例说明：
154
1542
1543
342
反过来也成立，共8条