P4319 Changing Roads

Xiao w and Xiao c are in Country H. In recent years, as Country H has developed, its roads have been constantly changing. According to Country H’s road law, every road has a value $w$, meaning that if Xiao w and Xiao c pass through this road, their $L$ value will decrease by $w$. However, if Xiao w and Xiao c have already passed this road before, their $L$ value will not decrease. Country H has $N$ cities. Initially, Country H has $N-1$ roads, and these $N-1$ roads form a tree. Xiao w and Xiao c will start from city $1$ and visit all cities of Country H. They will travel for 32766 days in total. For each day, they want the $L$ value to still be positive after finishing the tour. Find the minimum initial $L$ they need at departure for each day. All edges in Country H are undirected. No road connects a city to itself.

Line 1: an integer $N$. Lines 2 to $N$: each line contains three positive integers $u, v, w$, meaning there is a road of value $w$ between cities $u$ and $v$. Line $N+1$: an integer $M$, meaning Country H has $M$ roads that are changing. Lines $N+2$ to $N+M+1$: each line contains $5$ integers $u, v, w, l, r$, meaning there is a road of value $w$ from city $u$ to city $v$, and this road exists from day $l$ to day $r$.

Output $32766$ lines. The $i$-th line is the minimum $L$ required on day $i$.

On day 1, choose $1 \xrightarrow{1} 2 \xrightarrow{0} 1 \xrightarrow{3} 3 \xrightarrow{2} 4$. The $L$ value decreases by $6$ in total, so the minimum $L$ is $7$. On day 2, choose $1 \xrightarrow{1} 2 \xrightarrow{0} 1 \xrightarrow{3} 3 \xrightarrow{4} 4$. The $L$ value decreases by $8$ in total, so the minimum $L$ is $9$. From day 3 onward, choose $1 \xrightarrow{3} 3 \xrightarrow{4} 4 \xrightarrow{5} 2$. The $L$ value decreases by $12$ in total, so the minimum $L$ is $13$. Subtask 1: 15 points, $N = 100$, rm = 233. Subtask 2: 15 points, $N = 1000$, rm = 2333. Subtask 3: 20 points, $N = 49998$, rm = 32766, $l = r$. Subtask 4: 20 points, $N = 49999$, rm = 32766, $r = rm$. Subtask 5: 30 points, $N = 50000$, rm = 32766. For subtask 3, $M = rm$; for other subtasks, $M = 3 \times rm$. Constraints for all testdata: $1 \leq N \leq 50000$, $1 \leq l \leq r \leq rm \leq 32766$, $1 \leq w \leq 10^9$. Translated by ChatGPT 5