You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

最小游历费用

题目描述

你正在一个城市进行自驾游，这个城市有 $n$ 个景点编号为 $1$ 到 $n$。你打算按编号从小到大顺序游览每个景点。这些景点之间由$n-1$条高速公路连接成一个整体。

经过高速公路需要收费。第 $i$ 条高速有单程票（只能用一次）价格 $c_{i1}$ 和多程票（可以用无限次）价格 $c_{i2}$。你在旅游途中可能会重复走一条高速公路，所以多程票有时更划算。

请你求出从 $1$ 游览到 $n$ 最少需要多少费用。

输入格式

第一行为一个正整数 $n$。接下来的 $n-1$ 行描述 $n-1$ 条高速公路：有 $4$ 个正整数 $a_i,b_i,c_{i1},c_{i2}$，表示有一条连接 $a_i$ 和 $b_i$ 的单程票价格为 $c_{i1}$、多程票价格为 $c_{i2}$ 的边。

输出格式

一行一个正整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

10

样例 #2

样例输入 #2

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

样例输出 #2

16

样例 #3

样例输入 #3

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

样例输出 #3

11

提示

样例解释1：

购票方案如下：

$1\to 2$：多程票，费用 $5$。

$2\to 1\to 3$：$2\to 1$ 使用买过的多程票，无费用；$1\to 3$ 单程票，费用 $2$。

$3\to 1\to 2\to 4$：$3\to 1$ 单程票，费用 $2$；$1\to 2$ 使用买过的多程票，无费用；$2\to 4$ 单程票，费用 $1$。

费用共 $5+2+2+1=10$。

数据范围

对所有数据，$2\leq n\leq 100000$，$1\leq a_i,b_i\leq n$，$1\leq c_{i1}\leq c_{i2}\leq 100000$。

特殊性质A：这棵树是一条链

特殊性质B：这棵树的其中一个DFS序是$1$~$n$