P6869 [COCI 2019/2020 #5] Putovanje

You are given a tree with $n$ nodes, numbered from $1$ to $n$. You will visit each node in increasing order of its label. Traversing edges in the tree costs money. For the $i$-th edge, there is a single-use ticket (can only be used once) with price $c_{i1}$, and a multi-use ticket (can be used an unlimited number of times) with price $c_{i2}$. During your trip, you may traverse an edge multiple times, so a multi-use ticket can sometimes be more cost-effective. Please find the minimum total cost required to visit from $1$ to $n$.

- The first line: a positive integer $n$. - The next $n-1$ lines describe the $n-1$ edges: four positive integers $a_i, b_i, c_{i1}, c_{i2}$, meaning there is an edge connecting $a_i$ and $b_i$ whose single-use ticket costs $c_{i1}$ and multi-use ticket costs $c_{i2}$.

Output one line with one positive integer: your answer.

### Sample #1 Explanation - $1\to 2$: multi-use ticket, cost $5$. - $2\to 1\to 3$: $2\to 1$ uses the previously bought multi-use ticket, no cost; $1\to 3$ single-use ticket, cost $2$. - $3\to 1\to 2\to 4$: $3\to 1$ single-use ticket, cost $2$; $1\to 2$ uses the previously bought multi-use ticket, no cost; $2\to 4$ single-use ticket, cost $1$. - Total cost is $5+2+2+1=10$. ### Constraints **This problem uses bundled testdata.** - For $20 pts$ of the testdata, $2\leq n\leq 2000$. - For another $25 pts$ of the testdata, each town is directly connected to at most two other towns. - For all testdata, $2\leq n\leq 2\times10^5$, $1\leq a_i, b_i\leq n$, $1\leq c_{i1}\leq c_{i2}\leq 10^5$. ### Notes **Translated from [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #5](https://hsin.hr/coci/archive/2019_2020/contest5_tasks.pdf) _T4 Putovanje_.** Translated by ChatGPT 5