{"problem":{"name":"L. Sunrise","description":{"content":"The AGM realm consists of $1 <= N <= 10^5$ cities, indexed from $1$ to $N$. This year there is a special sunrise, so everyone wants to see it. The sunrise can be seen just from the city D. The cities ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10256L"},"statements":[{"statement_type":"Markdown","content":"The AGM realm consists of $1 <= N <= 10^5$ cities, indexed from $1$ to $N$. This year there is a special sunrise, so everyone wants to see it. The sunrise can be seen just from the city D. The cities from AGM realm are connected with $N$ directed roads and each road is of type $1$ or type $2$. Each city $i$ has cars of power $1 <= v a l_i <= 2 * 10^5$. Everyone wants to travel from their city to city $D$ using the cars. If you are using a car with power $x$, the cost to traverse a road of type $1$ is $x$, and the cost to traverse a road of type $2$ is $x^2$. If you start your journey from city $i$, you will start with a car of power $v a l_i$. When reaching a city $j$ on your route you have the opportunity to change your car with one of power $v a l_j$ with a cost of $-10^(13) <= t a x_j <= 10^(13)$. The journey stops as soon as you reach city $D$, but you can still change your car in this city. You can't change the car in the city where you start the journey from.\n\nFor each city $1 <= i <= N$, you need to compute the minimum cost to reach city $D$ starting from city $i$. It is guaranteed that city $D$ is reachable from all the cities. \n\nThe first line of the input will contain the number $N$ ($1 <= N <= 10^5$), representing the number of cities, and the number $D$ ($1 <= D <= N$), representing the city where the sunrise can be seen.\n\n The following $N$ lines will contain two numbers $x_i$ ($1 <= x_i <= N$, $x_i eq.not i$) and $t_i$ ($1 <= t_i <= 2$) each, representing that there exists a directed road from city $i$ to city $x_i$ of type $t_i$.\n\n The line $N + 1$ will contain $N$ numbers, the array $v a l$ ($1 <= v a l_i <= 2 * 10^5$). Where $v a l_i$ represents the power of the cars from city $i$. \n\n The line $N + 2$ will contain $N$ numbers, the array $t a x$ ($-10^(13) <= t a x_i <= 10^(13)$). Where $t a x_i$ represents the cost to change the car in city $i$.\n\nYou should output one line consisting of $N$ numbers, representing the minimum cost to reach city D starting from city $i$, for each $1 <= i <= N$ (Note that this cost can be negative too).\n\nThe journey with minimum cost from city 4: \n\n You start with a car with power 3 and travel to city 1 with this power, it will cost you $3^2 = 9$. \n\n In city 1 you change the car with one with power 5 and it will cost you -10. \n\n Then you travel to city 2 with this power, it will cost you 5. \n\n In city 2 you change the car with one with power 2 and it will cost you 4. \n\n Then you travel to city 3 with this power, it will cost you $2^2 = 4$. \n\n And in city 3 you change the car and it will cost you -4. \n\n The total cost of the journey is 8.\n\n## Input\n\nThe first line of the input will contain the number $N$ ($1 <= N <= 10^5$), representing the number of cities, and the number $D$ ($1 <= D <= N$), representing the city where the sunrise can be seen. The following $N$ lines will contain two numbers $x_i$ ($1 <= x_i <= N$, $x_i eq.not i$) and $t_i$ ($1 <= t_i <= 2$) each, representing that there exists a directed road from city $i$ to city $x_i$ of type $t_i$. The line $N + 1$ will contain $N$ numbers, the array $v a l$ ($1 <= v a l_i <= 2 * 10^5$). Where $v a l_i$ represents the power of the cars from city $i$.  The line $N + 2$ will contain $N$ numbers, the array $t a x$ ($-10^(13) <= t a x_i <= 10^(13)$). Where $t a x_i$ represents the cost to change the car in city $i$.\n\n## Output\n\nYou should output one line consisting of $N$ numbers, representing the minimum cost to reach city D starting from city $i$, for each $1 <= i <= N$ (Note that this cost can be negative too).\n\n[samples]\n\n## Note\n\nThe journey with minimum cost from city 4:  You start with a car with power 3 and travel to city 1 with this power, it will cost you $3^2 = 9$.  In city 1 you change the car with one with power 5 and it will cost you -10.  Then you travel to city 2 with this power, it will cost you 5.  In city 2 you change the car with one with power 2 and it will cost you 4.  Then you travel to city 3 with this power, it will cost you $2^2 = 4$.  And in city 3 you change the car and it will cost you -4.  The total cost of the journey is 8.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of dragon lairs.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the gold obtained from defeating the $ i $-th dragon.  \n\nLet $ S \\subseteq \\{1, 2, \\dots, n\\} $ be the set of indices of dragons the hero defeats, in order.  \nLet $ k = |S| $ be the number of battles fought.  \nLet the battles occur at positions $ i_1 < i_2 < \\dots < i_k $, corresponding to the sequence of defeated dragons.  \n\n**Constraints**  \n1. The hero must traverse the road in order: if $ i_j \\in S $, then all $ i < i_j $ are considered before $ i_j $.  \n2. The cost of the $ m $-th battle (in chronological order of battles) is $ m $ gold.  \n3. At every point in time, the hero’s gold balance must be non-negative:  \n   $$\n   \\sum_{j=1}^m a_{i_j} - \\sum_{j=1}^m j \\geq 0 \\quad \\text{for all } m = 1, \\dots, k.\n   $$\n\n**Objective**  \nMaximize the final profit:  \n$$\n\\max_{S \\subseteq \\{1,\\dots,n\\}} \\left( \\sum_{i \\in S} a_i - \\frac{|S|(|S|+1)}{2} \\right)\n$$  \nsubject to the non-negativity constraint on the partial sums at every battle.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10256L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}