[COCI2019-2020#5] Putovanje

题目描述

给你一棵有 $n$ 个点的树,节点编号从 $1$ 到 $n$。 你会按编号从小到大顺序访问每个节点。 经过树上的边需要收费。第 $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

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

输出样例 #1

10

输入样例 #2

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

输出样例 #2

16

输入样例 #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$。 ### 数据范围 **本题捆绑测试。** - 对于 $20 pts$ 的数据,$2\leq n\leq 2000$。 - 对于另外 $25 pts$ 的数据,每个城镇最多与另外两个城镇直接相连。 - 对于所有的数据,$2\leq n\leq 200000$,$1\leq a_i,b_i\leq n$,$1\leq c_{i1}\leq c_{i2}\leq 100000$。 ### 说明 **题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #5](https://hsin.hr/coci/archive/2019_2020/contest5_tasks.pdf) _T4 Putovanje_**。