P8117 "Wdoi-1.5" Traveler 1977.

A brilliant arc streaked across the deep starry sky, and then merged into this vast realm. Travelers of the 20th century, carrying both hope and unease, flew toward outer space. This is a gift from a distant, tiny world. On it are recorded our voices, our science, our images, our music, our thoughts, and our emotions. We tried our best to live through our time, and enter your time. Perhaps humanity will lose contact with it, and it will, like a drifting bottle, walk alone toward the depths of the universe, until it is picked up by “another person”. And the last “selfie” it left for us is only a pale blue dot of $0.12$ pixels — the only home we know so far. $\kern{80pt}$ $$\scriptscriptstyle\text{Pale Blue Dot, Voyager 1, February 14, 1990}$$ “I can’t tell reality from dreams anymore.” “Maybe the boundary between dreams and reality was never that clear.” …… “Seriously, Renko, didn’t you say you’re close to starlight and the moon? Why don’t you look up for once?” I was about to add a few more lines to the notebook, when the moonlight I used to see suddenly dimmed. Golden hair hanging down in front of my eyes blocked my view. I coughed lightly, raised my hand and waved in front of me to drive it out of my sight, then turned to look behind me. The girl in a white hat in front of me was my companion, Merry. I often tease her for having strange eyes that can see the “boundary” that we cannot. Although my own eyes are also special — I can tell where and when we are just by starlight and the moon. Oh, and we are a student secret club called “Hifuu Club”, dedicated to exploring the hidden barriers under the scientific century. On this summer night, wanting to fulfill my promise to her, I came out into the wild to observe the movement of celestial bodies. “What are you thinking about?” That is hard to answer. But since I had agreed to come out with Merry today to watch the starry sky, it was only natural that my thoughts would be led to people’s past exploration and desire to know. “Um, I’m thinking about the origin of our current scientific century.” “Huh? Renko, aren’t you studying physics? Why are you suddenly thinking about that kind of question?” Merry tilted her head to the right. I pointed to the sky, and she sat down beside me, casting her gaze into the brilliant sea of stars. “Um, I’m thinking about the origin of our current scientific century. Do you remember the two travelers I told you about?” “Voyager 1 and Voyager 2?” “Exactly. Even now, no one has named any deep-space project ‘Voyager’. With such a poetic and emotional name, they represent people’s expectations for the future and their desire for truth. Facing the unknown and confusion, they rushed into the sea of stars without hesitation.” Merry stood up and raised her binoculars. Her figure moved back and forth in the dim and quiet night. The pale, halo-like moonlight shone through gaps in the leaves and branches above, leaving patches of light on her, a sight that made one feel intoxicated. A supernova explosion is the end of a star’s life, and also the beginning of new stars’ lives. Who can say science has reached the end, and that things that cannot be explained do not exist? The core of science lies in those things that are regarded as illusions, hidden in the fog, and it is by no means what those arrogant old men say: that science is everything we already know and have mastered. To us, this is obvious. Following the footsteps of the first club president, we explore the barriers scattered everywhere, seeking a corner of the truth hidden behind the unknown — it is precisely because of this belief. Time passed. Specks of stardust circled around Polaris. If you look carefully, Polaris is also moving slightly. In front of my sight, Merry excitedly exclaimed at meteors radiating from Perseus, occasionally streaking across the sky. I could not help but think: now Kochab serves as the closest star to the north celestial pole and takes on the responsibility of guiding travelers, but in eternal motion there will always be new puzzles, new unknowns, and new exploration waiting for us to discover. So it is with things; so it is with events; so it is with people. The road ahead always has unknown things waiting for us to explore. If all secrets were solved, then there would be nothing left afterward. Knowing everything is merely empty nothingness. The unknown is the driving force of humanity $\scriptscriptstyle{}^{[{\color{grey}{1}}]}$. We hope to be like those two pioneers: as trailblazers, to awaken the curiosity and spirit of exploration rooted in people’s hearts toward the unknown, and to pass it on like a torch. Though the body is but a speck under the sky, the heart yearns for the stars like dust. Merry beside me leaned against a tree, already breathing in a steady rhythm, her body rising and falling slightly. I reached out, moved her hand aside, brushed away her hanging hair, and took out her notebook. >From night to morning. From morning to night. From reality to dreams. From dreams to reality. One day, in a dream, we will encounter that unobserved starry sky.$\scriptscriptstyle{}^{[{\color{grey}{2}}]}$ $\scriptscriptstyle{[1],[2]}\text{：Quoted from }$ [here](https://bbs.nyasama.com/forum.php?mod=viewthread&tid=308054&page=2)

The deep starry sky can be regarded as a directed graph, where the nodes are stars. Nodes have no weights, and edges have weights. The graph has $n$ nodes and $m$ edges, and it may contain multiple edges and self-loops. However, it is guaranteed that there exists at least one path from $s$ to $t$ (given in the input). For the $i$-th directed edge, its start point is $u_i$, its end point is $v_i$, and its weight is represented by an ordered triple $(l_i,r_i,w_i)$. Renko starts from node $s$ and reaches node $t$ after traversing some edges. She carries an array $a$ of length $k$ with an initial value of $0$ everywhere. Each time she traverses edge $i$, she performs the operation of adding $w_i$ to the interval $[l_i,r_i]$ of array $a$. She uses a segment tree **with lazy tags** to maintain this operation. The segment tree implementation is given below. You need to construct a path from $s$ to $t$ such that when reaching node $t$, the sum of all tags on the segment tree is minimized. Output this minimum value. Below is the pseudocode of the segment tree (for convenience, the C++ source code of the segment tree is provided in the attachment): $$ \begin{array}{l}\hline\hline\\[-0.8em] \textbf{Algorithm: }\text{SegTree}\\\hline\\[-0.5em] \begin{array}{rl} 1& \mathbf{Input.} \text{ An array $a$ of length $k$, initially all $0$}\\ 2& \mathbf{Output.} \text{ The result after performing several range-add operations on $a$}\\ 3& \mathbf{Method.}\\ 4& \mathrm{Add}(L,R,x)\\ 5& \quad\mathrm{Add0}(L,R,x,root,1,k)\\ 6& \mathrm{Add0}(L,R,x,u,l,r)\\ 7& \quad\mathbf{if}\ L \le l\ \mathbf{and}\ r\le R\\ 8& \quad\quad \mathrm{tag}(u) \gets \mathrm{tag}(u) + x\\ 9& \quad\quad \mathbf{return}\\ 10& \quad mid \gets \lfloor\frac{l+r} 2\rfloor\\ 11& \quad \mathrm{tag}(\mathrm{lson}(u)) \gets \mathrm{tag}(\mathrm{lson}(u))+\mathrm{tag}(u)\\ 12& \quad \mathrm{tag}(\mathrm{rson}(u)) \gets \mathrm{tag}(\mathrm{rson}(u))+\mathrm{tag}(u)\\ 13& \quad \mathrm{tag}(u) \gets 0\\ 14& \quad\mathbf{if}\ L \le mid\\ 15& \quad\quad\mathrm{Add0}(L,R,x,\mathrm{lson}(u),l,mid)\\ 16& \quad\mathbf{if}\ mid < R\\ 17& \quad\quad\mathrm{Add0}(L,R,x,\mathrm{rson}(u),mid+1,r)\\ \end{array}\\\hline\hline \end{array} $$

- The first line contains five integers $n,m,k,s,t$. - The next $m$ lines each contain five integers $u_i,v_i,l_i,r_i,w_i$.

- One line with one integer, representing the sum of the weights of all lazy tags on the segment tree after traveling along your constructed path from $s$ to $t$.

### Sample Explanation #### Sample \#1  It is easy to see that in Sample $1$ there are exactly two possible paths: $1\to 2\to 4$ and $1\to 3\to 4$. Below we compute the final sum of $\text{tag}$ values for these two paths.  Consider drawing this segment tree with $k=5$.  After taking edge $1\to 2$, the node $[1,2]$ is assigned a $\text{tag}$ with value $2$.  After taking edge $2\to 4$, nodes $[2,2]$ and $[3,3]$ are assigned $\text{tag}$ values of $1$. However, the tag of node $[1,2]$ is pushed down (because when adding $1$ to interval $[2,3]$, node $[1,2]$ is visited, and since $[1,2]\nsubseteq[2,3]$, a pushdown happens). Therefore, the $\text{tag}$ values of nodes $[1,1]$ and $[2,2]$ are each increased by $2$, ending up as shown in the figure. Thus, after reaching $4$, the sum of $\text{tag}$ over all nodes is $2+3+1=6$. ---  For the other path, first add $1$ to $[4,5]$.  Then add $2$ to $[3,5]$. No pushdown occurs for any node that has a $\text{tag}$, so the final total is $2+3=5$. Since $6>5$, the final answer is $5$. ### Constraints and Conventions $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|}\hline \textbf{subtask}& \textbf{Score}& {\bm n\le} & {\bm m\le} & {\bm k\le} & \textbf{Special Properties} & \textbf{subtask Dependencies}\cr\hline 1 & 10& 10 & 30 & 5 & - & -\cr\hline 2 & 5&30 & 30 & 12 & \textbf{AB} &-\cr\hline 3 & 20&30 & 500 & 12 & \textbf{B} &2 \cr\hline 4 & 15&200 & 3\times 10^3 & 25 & \textbf{B}&3\cr\hline 5 & 50&200 & 3\times 10^3 & 25 & - &4\cr\hline \end{array} $$ - **Special Property** $\textbf{A}$: It is guaranteed that there is exactly one path from $s$ to $t$. - **Special Property** $\textbf{B}$: It is guaranteed that the graph has no cycles. For $100\%$ of the testdata: $1 \le s,t,u_i,v_i \leq n \leq 200$, $1 \leq m \leq 3\times 10^3$, $1 \leq l_i\le r_i \leq k \leq 25$, $1 \leq w_i \leq 10^3$. ### Notes There are two versions of the segment tree in the attachment. The $\text{Lite}$ version **only** includes the pushdown operation for lazy tags that you will use in this problem, while the standard version more completely supports range add and range sum queries. You may use either version according to your preference. Translated by ChatGPT 5