Background

Little C is the one who always wins.

Every Wednesday night, Little T is eating pork trotter rice, while Little C is having dinner with a girl in the cafeteria.

Every Friday night, Little T starts up the Ruins Library, while Little C is chatting with a girl.

Today, Little T is sleeping, and Little C is playing checkers that humans always win with a girl.

Problem Description

Given a tree with $n$ vertices. Each edge has a weight, and the weight is a triple. The triple of the $i$-th edge is $e=(e_{i,1},e_{i,2},e_{i,3})$.

Define the function $\operatorname{win}(x,y)$:

• If $x_2<y_2$ and $x_3<y_3$, then $\operatorname{win}(x,y)=x_1$.
• If $x_2>y_2$ and $x_3>y_3$, then $\operatorname{win}(x,y)=y_1$.
• Otherwise, $\operatorname{win}(x,y)=0$.

Here $x=(x_1,x_2,x_3)$ and $y=(y_1,y_2,y_3)$.

Obviously, the function $\operatorname{win}$ is commutative.

For a triple sequence $\{a_n\}$, define its value as $\max_{i=1}^{n-1} \operatorname{win}(a_i,a_{i+1})$. In particular, when $n=1$, its value is $0$.

Define the value of a path as the value of the sequence formed by the weights of all edges on the path in order.

Compute the sum of values over all undirected paths in the tree.

Input Format

The first line contains a positive integer $n$（$1 \le n\leq 3\times 10^5$）, denoting the number of vertices in the tree.

The next $n-1$ lines each contain four integers $u,v,e_{i,1},e_{i,2}$, where $e_{i,3}=i$.

It is guaranteed that $\{e_{i,1}\}$ are pairwise distinct, and $\{e_{i,2}\}$ are pairwise distinct. Their values are all in $[1,n]$.

Output Format

Output one integer on one line, denoting the answer.

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

9

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

Hint

One set of hack testdata was added on 2025/10/31.

Translated by ChatGPT 5