题目背景

小 C 是人赢。

每周三晚上，小 T 晚上在吃猪脚饭，小 C 晚上和妹子在食堂共进晚餐。

每周五晚上，小 T 启动废墟图书馆，小 C 在和妹子聊天。

今天小 T 在睡觉，而小 C 在和妹子玩人赢的跳棋。

题目描述

给一棵 $n$ 个点的树，边有边权，边权为三元组。第 $i$ 条边的三元组 $e$ 为 $(e_{i,1},e_{i,2},e_{i,3})$。

设函数 $\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$。

其中 $x=(x_1,x_2,x_3),y=(y_1,y_2,y_3)$。

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

设一个三元组序列 $\{a_n\}$ 的权值为 $\max_{i=1}^{n-1} \operatorname{win}(a_i,a_{i+1})$，特别的，$n=1$ 时权值为 $0$。

设一条路径的权值为经过的所有边的权值按顺序组成的序列的权值。

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

输入格式

第一行一个正整数 $n$（$1 \le n\leq 3\times 10^5$） 表示树的节点数。

之后 $n-1$ 行每行四个整数表示 $u,v,e_{i,1},e_{i,2}$，其中有 $e_{i,3}=i$。

保证 $\{e_{i,1}\}$ 和 $\{e_{i,2}\}$ 是一个 $1\sim n-1$ 的排列。

输出格式

一行一个整数表示答案。

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