题目描述

给定一棵有 $n$ 个节点的树，树边带权，每条边的权值是一个三元组。

第 $i$ 条边的权值记为

定义函数 $\operatorname{win}(x,y)$，其中

函数值如下：

• 若 $x_2<y_2$ 且 $x_3<y_3$，则

  $$\operatorname{win}(x,y)=x_1;$$

• 若 $x_2>y_2$ 且 $x_3>y_3$，则

  $$\operatorname{win}(x,y)=y_1;$$

• 否则

  $$\operatorname{win}(x,y)=0.$$

显然，$\operatorname{win}$ 函数满足交换律。

对于一个三元组序列

定义该序列的权值为

特别地，当 $k=1$ 时，序列的权值为 $0$。

一条树上路径的权值，定义为该路径依次经过的所有边的三元组权值所组成序列的权值。

求树上所有无向路径的权值之和。

输入格式

第一行包含一个正整数 $n$，表示树的节点数。

接下来 $n-1$ 行，第 $i$ 行包含四个整数

表示节点 $u$ 与节点 $v$ 之间存在第 $i$ 条边，且该边三元组的第三个分量满足

保证序列

和

均为 $1,2,\ldots,n-1$ 的一个排列。

输出格式

输出一行一个整数，表示答案。

样例 1

输入

5
1 2 1 2
1 3 2 1
1 4 3 3
1 5 4 4

输出

9

样例 2

输入

7
1 2 3 4
2 3 6 2
2 4 1 3
2 5 4 6
3 6 2 1
5 7 5 5

输出

44

数据范围与提示

• 对于 $25\%$ 的数据，$n\le 1000$；

• 对于 $75\%$ 的数据，$n\le 10^5$；

• 对于全部测试数据，

  $$1\le n\le 3\times 10^5.$$

  并保证 $\{e_{i,1}\}$ 和 $\{e_{i,2}\}$ 均为 $1,2,\ldots,n-1$ 的一个排列。