1942.md (46601B)
1 Source: https://codeforces.com/blog/entry/126942 2 3 Thank you for participating! We put a lot of effort into this contest. Special thanks to [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") for contributing to these problems. 4 5 **Rating Predictions** 6 7 | Person | A | B | C1 | C2 | D | E | F | G | H | 8 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 9 | [oursaco](/profile/oursaco "International Master oursaco") | 800 | 1200 | 1500 | 1800 | 2200 | 2400 | 2800 | 2700 | 3400 | 10 | [priyanshu.p](/profile/priyanshu.p "Expert priyanshu.p") | 800 | 1200 | 1300 | 1600 | 2200 | | | | | 11 | [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") | 800 | 1200 | 1400 | 1700 | 2100 | 2300 | 2900 | 2900 | 3500 | 12 | [cry](/profile/cry "Candidate Master cry") | 800 | 1000 | 1300 | 1700 | 2100 | 2200 | 2800 | 2900 | 3500 | 13 | [buffering](/profile/buffering "Expert buffering") | 800 | 1000 | 1500 | 1900 | 2100 | 2200 | 2700 | 2800 | 3500 | 14 | [JagguBandar](/profile/JagguBandar "Master JagguBandar") | 800 | 1200 | 1700 | 2000 | 1800 | 2300 | | | | 15 | [omeganot](/profile/omeganot "Master omeganot") | 900 | 1000 | 1400 | 1800 | 2200 | 2300 | 2600 | | | 16 | [drdilyor](/profile/drdilyor "Master drdilyor") | 800 | 1300 | 1500 | 1800 | 2100 | 2200 | | | | 17 | [jay_jayjay](/profile/jay_jayjay "Master jay_jayjay") | 900 | 1400 | 1300 | 1600 | 1800 | 2300 | 2600 | 2800 | 3500 | 18 | [chromate00](/profile/chromate00 "Expert chromate00") | 900 | 1300 | 1400 | 1700 | 2200 | 2400 | 2700 | 2900 | 3400 | 19 | [maxrgby](/profile/maxrgby "Candidate Master maxrgby") | 800 | 1200 | 1300 | 1700 | 2100 | | | | | 20 | [SunShine11](/profile/SunShine11 "Expert SunShine11") | 800 | 1300 | 1500 | 1800 | 2100 | | | | | 21 | [MridulAhi](/profile/MridulAhi "Master MridulAhi") | 800 | 1200 | 1500 | 2000 | 1900 | 2200 | 2600 | 2800 | | 22 | [WAtoAC2001](/profile/WAtoAC2001 "Master WAtoAC2001") | 800 | 1300 | 1600 | 2000 | 2300 | | | 2800 | | 23 | [rainboy](/profile/rainboy "Master rainboy") | | | | | 2100 | 2400 | 2800 | 2700 | 3400 | 24 | [Geothermal](/profile/Geothermal "Legendary Grandmaster Geothermal") | 800 | 900 | 1300 | 1700 | 1800 | 2300 | 2600 | 2800 | 3500 | 25 | [lethan3](/profile/lethan3 "Master lethan3") | 800 | 1100 | 1500 | 1900 | 2200 | | | | | 26 | [awesomeguy856](/profile/awesomeguy856 "Master awesomeguy856") | 800 | 1200 | 1000 | 1500 | 2100 | 2100 | | 2400 | | 27 | [camc](/profile/camc "Master camc") | 800 | 1100 | 1500 | 1900 | 2100 | 2200 | | | | 28 | [rqi](/profile/rqi "International Grandmaster rqi") | 1000 | 1500 | 1600 | 1900 | 2000 | 2300 | 2700 | | | 29 | [sum](/profile/sum "Master sum") | | | | | 2000 | 2200 | 2600 | | | 30 31 | | A | B | C1 | C2 | D | E | F | G | H | 32 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 33 | Average | 811 | 1189 | 1455 | 1810 | 2100 | 2273 | 2709 | 2770 | 3463 | 34 | Actual | 800 | 1100 | 1300 | 1700 | 2100 | 2300 | 2700 | 2800 | 3500 | 35 36 #### Solutions 37 38 ##### [1942A - Farmer John's Challenge](/contest/1942/problem/A) 39 40 Problem Credits: [buffering](/profile/buffering "Expert buffering") 41 Analysis: [buffering](/profile/buffering "Expert buffering") 42 43 **Hint 1** 44 45 Solve for $k = 1$. 46 47 **Answer** 48 49 $a = 1, 2, 3 \dots n$ works. Why? 50 51 **Hint 2** 52 53 Solve for $k = n$. 54 55 **Answer** 56 57 $a = 1, 1, 1 \dots 1$ works. Why? 58 59 **Hint 3** 60 61 What other $k$ work for a given $n$? 62 63 **Answer** 64 65 Only $k = 1$ and $k = n$ have possible answers. 66 67 **Solution** 68 69 Read the hints. 70 71 For $k=1$, the construction $1,2,3\dots n$ will always work because in any other cyclic shift, $n$ will be before $1$. 72 73 Now, consider what happens if we want to find an array with two or more cyclic shifts that are sorted. If we consider two of these cyclic shifts, notice they are actually shifts of each other as well. 74 75 So, there should be a sorted array, and a shift of it which is also sorted. What this means is that some of the first elements in the array move to the back and stays sorted, which can **only happen if all values in the array are equal.** 76 77 If the array has all equal values, this gives us our construction for $k=n$. As we have seen, for $k \gt 1$, only $k=n$ is possible. Thus, for any other $k$ not equal to $1$ or $n$, we can print $-1$. 78 79 **Code (C++)** 80 81 ``` 82 #include <iostream> 83 using namespace std; 84 int main(){ 85 int t; cin >> t; 86 while(t--){ 87 int n, k; cin >> n >> k; 88 if(k == 1) for(int i = 0; i < n; i++) cout << i + 1 << " "; 89 else if(k == n) for(int i = 0; i < n; i++) cout << 1 << " "; 90 else cout << -1; 91 cout << "\n"; 92 } 93 } 94 ``` 95 96 ##### [1942B - Bessie and MEX](/contest/1942/problem/B) 97 98 Problem Credits: [buffering](/profile/buffering "Expert buffering") 99 Analysis: [buffering](/profile/buffering "Expert buffering") 100 101 Solution 1 102 103 **Hint 1** 104 105 We will construct the solution forward. 106 107 **Hint 2** 108 109 Separate the $a_i$'s given into negative and positive cases. What does this tell us about the $\texttt{MEX}$? 110 111 **Solution** 112 113 We can find $p_1, p_2, ... , p_n$ in order, looking at positive and negative cases. Note that $a_i \neq 0$ because $p_i$ would equal $\texttt{MEX}$($p_1 \dots p_i$), which can never happen. 114 115 * If $a_i \gt 0$, then $\texttt{MEX}$($p_1, p_2, ... p_i$) must increase from $\texttt{MEX}$($p_1, p_2, ... p_{i-1}$), so we know $p_i$ must equal $\texttt{MEX}$($p_1, p_2, ... p_{i-1}$). 116 * Otherwise, the $\texttt{MEX}$ stays the same, so $p_i$ is just simply $\texttt{MEX}$($p_1, p_2, ... p_{i-1}$) — $a_i$. 117 118 Thus, we can just maintain the $\texttt{MEX}$ and find each $p_i$ as we go forward. 119 120 **Here's more justification about specific differences leading to specific MEX changes** 121 122 There are only 2 things the $\texttt{MEX}$ can do: increase or stay the same (it can never decrease since larger prefixes contain smaller ones). 123 124 * In the case of a positive difference, consider what would happen if the $\texttt{MEX}$ stayed the same. Since the difference is positive, the $\texttt{MEX}$ would have to be greater than the current value, which is impossible because that value had to appear earlier on in the prefix. Since the $\texttt{MEX}$ is calculated on a permutation that can’t happen. So the $\texttt{MEX}$ has to increase. 125 126 * In the case of a negative value, the $\texttt{MEX}$ has to be less than the current value. But if it increased that means the current value changed its the $\texttt{MEX}$, meaning its the $\texttt{MEX}$ is now at least (current value + 1) and it is actually greater. So it has to stay the same. 127 128 Note that this is also a way to show $p$ is always unique. 129 130 **Code (C++)** 131 132 ``` 133 #include <bits/stdc++.h> 134 using namespace std; 135 136 void solve(){ 137 int n; cin >> n; 138 vector<int> a(n); 139 for(int& i: a) cin >> i; 140 vector<int> p(n), has(n + 1); 141 int mex = 0; 142 for(int i = 0; i < n; i++){ 143 if(a[i] >= 0){ 144 p[i] = mex; 145 } 146 else{ 147 p[i] = mex - a[i]; 148 } 149 has[p[i]] = true; 150 while(has[mex]) mex++; 151 } 152 for(int i: p) cout << i << " "; 153 cout << "\n"; 154 } 155 156 int main(){ 157 cin.tie(0) -> sync_with_stdio(0); 158 int T = 1; 159 cin >> T; 160 while(T--) solve(); 161 } 162 163 /* /\_/\ 164 * (= ._.) 165 * / > \> 166 */ 167 ``` 168 169 Solution 2 170 171 **Hint 1** 172 173 We will construct the solution backwards. 174 175 **Hint 2** 176 177 The $\texttt{MEX}$ is determined at the last index, since all of $0, 1 \dots n-1$ appear in $p$. 178 179 **Solution** 180 181 Read the hints. 182 183 Since we know the $\texttt{MEX}$ of the last position is $n$, then $n - p_n = a_n$. From this equation, we can find that $p_n = n - a_n$. 184 185 Now, because we know $p_n$, we can determine the $\texttt{MEX}$ of the first $n-1$ numbers. Like how we found $p_n$, we can do a similar process for finding $p_{n-1}$. Doing this for $i = n, n - 1 \dots 1$ will get us a valid answer $p$. 186 187 Note that this is also a way to show $p$ is always unique. 188 189 ##### [1942C1 - Bessie's Birthday Cake (Easy Version)](/contest/1942/problem/C1) and [1942C2 - Bessie's Birthday Cake (Hard Version)](/contest/1942/problem/C2) 190 191 Problem Credits: [cry](/profile/cry "Candidate Master cry") 192 Analysis: [cry](/profile/cry "Candidate Master cry") 193 194 **Solution (Easy Version)** 195 196 Ignoring $n$ for now, let's just focus on the $x$ chosen vertices. Sort the $x$ vertices and connect adjacent vertices to form its own smaller polygon. By drawing out some cases or if you're familiar with triangulation ([video that proves by induction](https://www.youtube.com/watch?v=2x4ioToqe_c)), you can form $x - 2$ triangles by drawing diagonals in a polygon with $x$ vertices. If you don't know it, one possible construction that always work is fixing one vertex $v$ and drawing diagonals to every other vertex not adjacent to $v$. Now, let's consider the original $n$-sided polygon. In additional to the aforementioned construction, to close the $x$-sided polygon up: for every non-adjacent vertex in the chosen vertices based on the bigger $n$-sided polygon, draw a diagonal between them. Through this construction, we can always guarantee $x - 2$ triangles. 197 198 However, this doesn't account for all triangles, as some triangles can form sides with the bigger $n$-sided polygon. These triangles occur exactly when two adjacent vertex in $x$ have exactly one vertex not in $x$ between them but part of the bigger polygon. This is because one side is from the diagonals we drew, and the other two sides form from the $n$-sided polygon. 199 200 Therefore, the answer is $x - 2$ + (number of adjacent chosen vertices $2$ apart). Note that the first chosen vertex is also adjacent to last chosen vertex in $x$. 201 202 **Solution (Hard Version)** 203 204 Read the solution to the easy version first. 205 206 We can now reduce the problem to the following: For every vertex we choose, we can make one more triangle. For every chosen vertices two apart, we can make one more triangle. Let's focus on the latter condition. To maximize the effect of our $y$ vertices, we want to prioritize vertices $v$ that satisfy the following: the vertex is not included in $x$ and there is a chosen vertex two apart. Let's denote such $v$ as good. 207 208 Let vertex $a$ and $b$ $(a \lt b)$ be adjacent chosen vertices in the $x$-sided polygon. There are $g = b - a - 1$ vertices for us to choose between them. There are two cases: if $g$ is odd, then we can choose $\lfloor \frac{g}{2} \rfloor$ vertices to form $\lfloor \frac{g}{2}\rfloor + 1$ extra triangles. This is because all of the vertices we choose will be good. if $g$ is even, then we can choose $\frac{g}{2}$ vertices to make $\frac{g}{2}$ extra triangles. This is because one of the vertices we choose will not be good. This shows that it is always optimal to process smaller and odd $g$ first. 209 210 After processing these adjacent gaps, if we have any leftover vertices, we can just ignore them. This is because since we have maximized the number of good vertices, even though any further vertex we place will increase the answer by $1$, it will break two good vertices which will decrease the answer by $1$. 211 212 **Code (C++)** 213 214 ``` 215 #include <bits/stdc++.h> 216 using namespace std; 217 218 void solve(){ 219 int n, x, y; cin >> n >> x >> y; 220 int initial_y = y; 221 vector<int> chosen(x); 222 for(int& i: chosen) cin >> i; 223 sort(chosen.begin(), chosen.end()); 224 int ans = x - 2; 225 int triangles_from_even_g = 0; 226 vector<int> odd_g; 227 auto process_gap = [&](int g) -> void{ 228 if(g <= 1){ 229 // already two apart 230 ans += g; 231 } 232 else if(g % 2 == 1){ 233 odd_g.push_back(g / 2); 234 } 235 else{ 236 triangles_from_even_g += g / 2; 237 } 238 }; 239 for(int i = 0; i < x - 1; i++){ 240 process_gap(chosen[i + 1] - chosen[i] - 1); 241 } 242 process_gap((chosen[0] + n) - chosen[x - 1] - 1); 243 sort(odd_g.begin(), odd_g.end()); 244 for(int g: odd_g){ 245 if(y >= g){ 246 // all vertices are good, so we can make g + 1 triangles 247 ans += g + 1; 248 y -= g; 249 } 250 else{ 251 ans += y; 252 y = 0; 253 break; 254 } 255 } 256 int even_triangles = min(triangles_from_even_g, y); 257 y -= even_triangles; 258 ans += even_triangles; 259 int used_vertices = initial_y - y; 260 ans += used_vertices; 261 cout << ans << "\n"; 262 } 263 264 int main(){ 265 cin.tie(0) -> sync_with_stdio(0); 266 int T = 1; 267 cin >> T; 268 while(T--) solve(); 269 } 270 271 /* /\_/\ 272 * (= ._.) 273 * / > \> 274 */ 275 ``` 276 277 #### [1942D - Learning to Paint](/contest/1942/problem/D) 278 279 Problem Credits: [sum](/profile/sum "Master sum") 280 Analysis: [sum](/profile/sum "Master sum") 281 282 **Hint 1** 283 284 We can solve this with dynamic programming. Let $\texttt{dp}[i]$ store a list of all $\min(k, 2^i)$ highest beauties of a painting in **non-increasing** order if you only paint cells $1,2,\ldots ,i$. 285 286 **Hint 2** 287 288 Transitioning boils down to finding the $k$ largest elements from $n$ **non-increasing** lists. Try to do this in $\mathcal{O}((n + k) \log n)$ time. 289 290 **Solution** 291 292 Let $\texttt{dp}[i]$ store a list of all $\min(k, 2^i)$ highest beauties of a painting in **non-increasing** order if you only paint cells $1,2,\ldots ,i$. 293 294 Let's define **merging** two lists as creating a new list that stores the $k$ highest values from the two lists. 295 296 First, let's look at a slow method of transitioning. We iterate over the left endpoint $l$ such that $l \ldots i$ is a maximal painted interval. At each $l$, we merge $\texttt{dp}[l - 2]$, with $a_{l,i}$ added to each value, into $\texttt{dp}[i]$. We also merge $\texttt{dp}[i - 1]$ into $\texttt{dp}[i]$ to handle the case in which we do not paint cell $i$. If implemented well, transitioning takes $\mathcal{O}(nk)$ time leading to an $\mathcal{O}(n^2k)$ solution which is too slow. 297 298 We can speed this up. This merging process boils down to finding the $k$ largest elements from $n$ **non-increasing** lists in $\mathcal{O}((n + k) \log n)$ time. We can use a priority queue that stores ($\texttt{element}, \texttt{index}$) for each list. We can do the following $k$ times: add the top of the priority queue to our answer, advance its index, and update the priority queue accordingly. This allows us to transition in $\mathcal{O}((n + k) \log n)$ time which leads to an $\mathcal{O}((n^2 + nk) \log n)$ solution. 299 300 Bonus: find an $\mathcal{O}(n^2 + k)$ solution. 301 302 **Code (C++)** 303 304 ``` 305 #include <bits/stdc++.h> 306 using namespace std; 307 308 void solve(){ 309 int n, k; 310 cin >> n >> k; 311 312 int A[n + 1][n + 1]; 313 314 for (int i = 1; i <= n; i++) 315 for (int j = i; j <= n; j++) 316 cin >> A[i][j]; 317 318 // dp[i] = Answer if we consider 1...i 319 vector<int> dp[n + 1]; 320 dp[0] = {0}; 321 322 for (int i = 1; i <= n; i++){ 323 priority_queue<array<int, 3>> pq; 324 325 // Don't create an interval 326 pq.push({dp[i - 1][0], i - 1, 0}); 327 328 // Create interval j+2...i (transition from j) 329 for (int j = i - 2; j >= -1; j--){ 330 pq.push({(j < 0 ? 0 : dp[j][0]) + A[j + 2][i], j, 0}); 331 } 332 333 while (pq.size() and dp[i].size() < k){ 334 auto [val, j, num] = pq.top(); pq.pop(); 335 dp[i].push_back(val); 336 337 if (j < 0 or num + 1 >= dp[j].size()) 338 continue; 339 340 // Don't create interval 341 if (j == i - 1) 342 pq.push({dp[i - 1][num + 1], i - 1, num + 1}); 343 344 // Create interval j+2...i (transition from j) 345 else 346 pq.push({dp[j][num + 1] + A[j + 2][i], j, num + 1}); 347 } 348 } 349 for (int i : dp[n]) 350 cout << i << " "; 351 cout << "\n"; 352 } 353 354 int main(){ 355 ios_base::sync_with_stdio(0); cin.tie(0); 356 int tc; 357 cin >> tc; 358 359 while (tc--) 360 solve(); 361 } 362 ``` 363 364 #### [1942E - Farm Game](/contest/1942/problem/E) 365 366 Problem Credits: [cry](/profile/cry "Candidate Master cry") 367 Analysis: [sum](/profile/sum "Master sum") 368 369 **Hint 1** 370 371 Think about the gaps between $(a_1,b_1), (a_2,b_2), ... ,(a_n,b_n)$. Let the gaps be $g_1,g_2,...,g_n$. What effect do the moves have on the gaps? 372 373 **Hint 2** 374 375 WLOG let the first cow be FJ's cow. FN wins if all $g_i$ are even. Otherwise FJ wins. Note that the game will always end. 376 377 **Hint 3** 378 379 Try to count the number of ways FN wins. We can iterate over the sum of $g_i$ and use stars and bars as well as other counting techniques. 380 381 **Solution** 382 383 Consider the gaps between $(a_1,b_1), (a_2,b_2), ... ,(a_n,b_n)$. In the example below, '$\texttt{a}$' represents FJ's cow, '$\texttt{b}$' represents FN's cow, and '$\texttt{.}$' represents an empty space. The gaps are $[2,3]$. 384 385 $\texttt{|.a..b....a...b.|}$ 386 387 Consider the gaps $g_1,g_2,...,g_n$. When a farmer moves, they choose some non-empty subset of non-zero $g_i$ and add or subtract $1$ from every element in the subset (so long such move is possible). The game ends when some farmer cannot move (which implies that all $g_i$ must be $0$ when the game ends). 388 389 WLOG let the first cow be FJ's cow. The winner of the game is determined as follows: 390 391 1) If all $g_i$ are even, then FN wins. If FJ pushes the cows corresponding to gaps $i_1, i_2, \ldots, i_k$ some direction in a move, then $g_{i_1}, g_{i_2}, \ldots g_{i_k}$ will change by $1$ and become odd. FN can then push the cows corresponding to gaps $i_1, i_2, \ldots, i_k$ **left** so that $g_{i_1}, g_{i_2}, \ldots g_{i_k}$ will become even again. Therefore, all $g_i$ will be even when it's FJ's turn and at least one $g_i$ will be odd when it's FN's turn. Since the game ends when all $g_i$ are $0$ (which is even), then FJ will lose. **Note that the game will always end.** This is since the sum of positions of FN's cows will always be decreasing since FN will always push some cow left. 392 393 2) Otherwise, FJ wins since he can subtract $1$ to all odd $g_i$ in his first move to make all elements even. Then it's FN's turn and all $g_i$ are even so by the reasoning above, FJ wins. 394 395 Let's use complementary counting and determine the number of ways **FN** wins (which is when all $g_i$ are even). We can iterate over the sum, $s$ ($s$ is even), of all $g_i$. At each $s$, we can use stars and bars to find how many such $g_1,g_2,...,g_n$ (all $g_i$ are even) sum to $s$. Specifically, the number of ways are $\frac{s}{2} + n - 1 \choose n - 1$. The number of ways to place the cows in the available positions given the gaps will be $2 \cdot {l - s - n \choose n}$. We multiply by $2$ since we can alternate starting with either FJ's cow or FN's cow. 396 397 Finally, we subtract this result from the total number of configurations, $2 \cdot {l \choose 2 \cdot n}$, to get the number of ways FJ wins. This runs in $\mathcal{O}(l)$ time. 398 399 **Code (C++)** 400 401 ``` 402 #include <bits/stdc++.h> 403 using namespace std; 404 405 #define ll long long 406 407 const int MAX = 2e6 + 5, MOD = 998244353; 408 409 ll fact[MAX], ifact[MAX]; 410 411 ll bpow(ll a, int p){ 412 ll ans = 1; 413 414 for (;p; p /= 2, a = (a * a) % MOD) 415 if (p & 1) 416 ans = (ans * a) % MOD; 417 418 return ans; 419 } 420 ll ncr(int n, int r){ 421 if (n < 0) 422 return 0; 423 if (r > n) 424 return 0; 425 426 return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD; 427 } 428 void solve(){ 429 int l, n; 430 cin >> l >> n; 431 432 ll all_even = 0; 433 434 for (int s = 0; s <= l; s += 2){ 435 all_even += 2 * ncr(s / 2 + n - 1, n - 1) % MOD * ncr(l - s - n, n) % MOD; 436 all_even %= MOD; 437 } 438 cout << (2 * ncr(l, 2 * n) % MOD - all_even + MOD) % MOD << "\n"; 439 } 440 441 int main(){ 442 ios_base::sync_with_stdio(0); cin.tie(0); 443 444 for (int i = 0; i < MAX; i++) 445 fact[i] = !i ? 1 : fact[i - 1] * i % MOD; 446 447 for (int i = MAX - 1; i >= 0; i--) 448 ifact[i] = (i == MAX - 1) ? bpow(fact[MAX - 1], MOD - 2) : ifact[i + 1] * (i + 1) % MOD; 449 450 int tc; 451 cin >> tc; 452 453 while (tc--) 454 solve(); 455 } 456 ``` 457 458 #### [1942F - Farmer John's Favorite Function](/contest/1942/problem/F) 459 460 Problem Credits: [sum](/profile/sum "Master sum") 461 Analysis: [sum](/profile/sum "Master sum") 462 463 **Hint 1** 464 465 Consider the case where all $f(i)$ are integers. Decreasing **any** $a_i$ will decrease $\lfloor f(n) \rfloor$. So solutions that iterate over the last few elements will not work. 466 467 **Hint 2** 468 469 If $n \ge 6$, changing $a_1$ will only affect $\lfloor f(n) \rfloor$ by at most $1$. 470 471 **Hint 3** 472 473 We can take the floor each time we square root. Specifically, we can define $f$ as: 474 475 * $f(1) = \lfloor \sqrt{a_1} \rfloor$ 476 * For all $i \gt 1$, $f(i) = \lfloor \sqrt{f(i-1)+a_i} \rfloor$ 477 478 This allows us to work with integers. 479 480 **Hint 4** 481 482 We can divide our array into blocks of size $b \ge 6$ (note that the value of $b$ depends on the solution). How can we use hint $2$? What should we store for each block? 483 484 **Solution** 485 486 Let's first look at the impact of earlier numbers on the final result. Earlier numbers can still influence $\lfloor f(n) \rfloor$ when $n$ is large. Suppose that all $f(i)$ are integers. Then decreasing **any** $a_i$ will decrease $\lfloor f(n) \rfloor$. 487 488 However, it is clear that the impact of earlier number on $\lfloor f(n) \rfloor$ is still extremely small. A key observation is that when $n \ge 6$, changing $a_1$ will only affect $\lfloor f(n) \rfloor$ by at most $1$. 489 490 Another observation is that we can take the floor each time we square root. Specifically, we can define $f$ as: 491 492 * $f(1) = \lfloor \sqrt{a_1} \rfloor$ 493 * For all $i \gt 1$, $f(i) = \lfloor \sqrt{f(i-1)+a_i} \rfloor$ 494 495 This allows us to work with integers. From here on, we work with this new definition of $f$. 496 497 Let's divide our array into blocks of size $b=6$. We can append zeroes to the front of the array to make $n$ a multiple of $b$. 498 499 Consider some block representing range $[l,r]$. Let's consider the subarray $a_l,a_{l+1},\ldots ,a_r$. Let $v$ be the value of $f(r)$ if we let $f(l - 1)=0$. Using our first observation, we know that $f(r)$ will be either $v$ or $v+1$ depending on $f(l - 1)$. So let's find the smallest value $c$ such that if $f(l - 1)=c$, then $f(r)=v+1$. This can be done by iterating over the elements of the block backwards. 500 501 For each block, we store its corresponding ($v,c$). We can build a segment tree over the blocks for an $\mathcal{O}((n + q) \log n)$ solution. 502 503 Alternatively, we can do square root decomposition by having $b=\sqrt n$ which leads to an $\mathcal{O}(n + q \sqrt n)$ solution (in practice, we should set $b$ to something small like $100$). 504 505 **Code (C++)** 506 507 **Segment Tree** 508 509 ``` 510 #include <bits/stdc++.h> 511 using namespace std; 512 513 #define ll long long 514 #define pll pair<ll, ll> 515 516 const int B = 6, MAX = 2e5 + B + 5; 517 518 int n, q, offset, numBlocks; ll A[MAX]; pll seg[MAX]; 519 520 pll comb(pll a, pll b){ 521 auto [vl, cl] = a; 522 auto [vr, cr] = b; 523 524 // Not defined 525 if (vl == -1) 526 return b; 527 if (vr == -1) 528 return a; 529 530 // Doesn't cross cutoff 531 if (vl < cr - 1) 532 return {vr, (ll)2e18}; 533 if (vl >= cr) 534 return {vr + 1, (ll)2e18}; 535 536 // If vl == cr - 1 537 return {vr, cl}; 538 } 539 void updSeg(int i, pll v){ 540 seg[i += numBlocks] = v; 541 542 for (i /= 2; i > 0; i /= 2) 543 seg[i] = comb(seg[i * 2], seg[i * 2 + 1]); 544 } 545 ll qry(int l = 0, int r = numBlocks - 1){ 546 pll retL = {-1, -1}; 547 pll retR = {-1, -1}; 548 549 for (l += numBlocks, r += numBlocks; l <= r; r /= 2, l /= 2){ 550 if (l % 2 == 1) 551 retL = comb(retL, seg[l++]); 552 if (r % 2 == 0) 553 retR = comb(seg[r--], retR); 554 } 555 return comb(retL, retR).first; 556 } 557 void updBlock(int blk){ 558 int l = blk * B; 559 int r = l + B - 1; 560 561 ll val = 0; 562 for (int i = l; i <= r; i++) 563 val = floor(sqrtl((long double)val + A[i])); 564 565 ll req = val + 1; 566 for (int i = r; i >= l; i--){ 567 if (req > 2e9){ 568 updSeg(blk, {val, (ll)2e18}); 569 return; 570 } 571 req = req * req - A[i]; 572 } 573 updSeg(blk, {val, req}); 574 } 575 576 int main(){ 577 ios_base::sync_with_stdio(0); cin.tie(0); 578 cin >> n >> q; 579 580 offset = (B - n % B) % B; 581 n += offset; 582 numBlocks = n / B; 583 584 for (int i = offset; i < n; i++) 585 cin >> A[i]; 586 587 for (int b = 0; b < numBlocks; b++) 588 updBlock(b); 589 590 while (q--){ 591 ll k, x; 592 cin >> k >> x; 593 k--; 594 k += offset; 595 596 A[k] = x; 597 updBlock(k / B); 598 599 cout << qry() << "\n"; 600 } 601 } 602 ``` 603 604 **Square Root Decomposition** 605 606 ``` 607 #include <bits/stdc++.h> 608 using namespace std; 609 610 #define ll long long 611 612 const int B = 100, MAX = 2e5 + B + 5; 613 614 int n, q, offset, numBlocks; ll A[MAX], val[MAX], cut[MAX]; 615 616 void buildBlock(int blk){ 617 int l = blk * B; 618 int r = l + B - 1; 619 620 ll cur = 0; 621 622 for (int i = l; i <= r; i++) 623 cur = floor(sqrtl((long double)cur + A[i])); 624 625 val[blk] = cur; 626 627 ll req = cur + 1; 628 629 for (int i = r; i >= l; i--){ 630 if (req > 2e9){ 631 cut[blk] = 2e18; 632 return; 633 } 634 req = req * req - A[i]; 635 } 636 cut[blk] = req; 637 } 638 ll qry(){ 639 ll cur = 0; 640 641 for (int b = 0; b < numBlocks; b++) 642 cur = (cur >= cut[b]) ? val[b] + 1 : val[b]; 643 644 return cur; 645 } 646 647 int main(){ 648 ios_base::sync_with_stdio(0); cin.tie(0); 649 cin >> n >> q; 650 651 offset = (B - n % B) % B; 652 n += offset; 653 numBlocks = n / B; 654 655 for (int i = offset; i < n; i++) 656 cin >> A[i]; 657 658 for (int b = 0; b < numBlocks; b++) 659 buildBlock(b); 660 661 while (q--){ 662 ll k, x; 663 cin >> k >> x; 664 k--; 665 k += offset; 666 667 A[k] = x; 668 buildBlock(k / B); 669 670 cout << qry() << "\n"; 671 } 672 } 673 ``` 674 675 #### [1942G - Bessie and Cards](/contest/1942/problem/G) 676 677 Problem Credits: [smax](/profile/smax "Grandmaster smax") 678 Analysis: [smax](/profile/smax "Grandmaster smax") 679 680 **Hint 1** 681 682 "Draw $1$" cards do not matter because we can immediately play them when we draw them. 683 684 **Hint 2** 685 686 Treat "draw $2$" as $+1$ and "draw $0$" as $-1$. We start with a balance of $+5$. We draw all the cards up to the first prefix where the balance dips to $0$. We are interested in the number of ways where the special cards lie in this prefix. 687 688 **Solution** 689 690 Read the hints. 691 692 Treat the special cards as "draw $0$" cards and multiply by the appropriate binomial coefficient at the end. Also treat cards of the same type as indistinguishable and multiply by the appropriate factorials at the end. 693 694 Enumerate the length of the prefix where the balance first hits $0$. This dictates how many $+1$ and $-1$ we have. Now we want to count the number of ways of arranging $+1$ and $-1$ such that the balance never dips to $0$, assuming we start with $+5$. 695 696 To solve this subproblem, we can draw inspiration from the [path counting interpretation](https://en.wikipedia.org/wiki/Catalan_number#Second_proof) for counting balanced bracket sequences. We have $n$ open and $n$ close brackets and want to count the number of balanced bracket sequences starting with `((((` (note that there are only $4$ instead of $5$ open brackets to shift from all balances being strictly positive to all balances being non-negative). The number of sequences ignoring the balance constraint is $\binom{2n-4}{n}$. Any bracket sequence where some balance dips negative corresponds to a path that walks above the line $y = x$. For those paths, we reflect over the line $y = x + 1$ at the first point where it steps over the line. So there is a bijection between these paths and paths that reach the point $(n-1,n+1)$, of which there are $\binom{2n-4}{n+1}$. So the total number of ways is $\binom{2n-4}{n} - \binom{2n-4}{n+1}$. 697 698 Our final answer is summing up the number of ways over all prefix lengths. Make sure to handle the case where you draw the entire deck correctly. The complexity is $\mathcal O(\min(a,c))$. 699 700 **Code (C++)** 701 702 #### [1942H - Farmer John's Favorite Intern](/contest/1942/problem/H) 703 704 Problem Credits: [oursaco](/profile/oursaco "International Master oursaco") 705 Analysis: [oursaco](/profile/oursaco "International Master oursaco") / [rainboy](/profile/rainboy "Candidate Master rainboy") 706 707 **Solution 1** 708 709 Model this as a flow problem where growth events are an input of some flow to a node and harvest events and the necessary amount of fruits are an output of flow to the sink. We will define the $a_i$ edge to be the input edge of every node, $b_i$ to be the output edge for necessary fruits, and $c_i$ to be the output edge for growth events. The connections for each individual node will look like: 710 711 $(\text{source}, a_i, \text{# of growth events})$ 712 713 $(a_i, \text{temporary node}, \text{INF})$ 714 715 $(\text{temporary node}, b_i, \text{INF})$ 716 717 $(\text{temporary node}, c_i, \text{INF})$ 718 719 $(b_i, \text{sink}, \text{# of required peaches})$ 720 721 $(c_i, \text{sink}, \text{# of harvest events})$ 722 723 To simulate growth events affecting the subtree, every temporary node has infinite capacity directed edges down to the temporary nodes of its children. To simulate growth events affecting the parent, every temporary node has an infinite capacity directed edge to its parent's $b_i$. To simulate harvest events affecting subtree, every node has infinite capacity directed edges to all its ancestors' $c_i$ nodes. Lets try to find the min cut of the graph. If we don't put cut some node's $a_i$, then we must cut both $b_i$ and $c_i$ for all of its descendants. If we don't cut some node's $a_i$, then we also must cut $c_i$ for all its ancestors and $b_i$ for its parent. Thus, we can model a $dp[i][0/1/2]$ to know if we are currently cutting the a_i input edge, cutting the b_i and c_i output edge, or cutting the a_i edge but there is some node in the subtree where we did not cut the a_i edge, in which case we need to cut the c_i edge as well. Transitions look like: 724 725 $dp[i][0] = a_i + \sum_j dp[j][0]$ 726 727 $dp[i][1] = b_i + c_i + \sum_j dp[j][1]$ 728 729 $dp[i][2] = a_i + c_i + \min(\sum_j \min(dp[j][0], dp[j][2]), b_i + \sum_j \min(dp[j][0], dp[j][1], dp[j][2]))$ where at least one child is a $dp[j][2]$ or $dp[j][1]$ 730 731 $dp[i][2]$ can be rewritten as: 732 733 $dp[i][2] = a_i + c_i + \min(\min(dp[j][2] - \min(dp[j][0], dp[j][2])) + \sum_j \min(dp[j][0], dp[j][2]),$ $\min(dp[j][1] - \min(dp[j][0], dp[j][1], dp[j][2])) + b_i + \sum_j \min(dp[j][0], dp[j][1], dp[j][2])))$ 734 735 Use dynamic dp by representing dp transitions as a matrix where all the light children dp values are known and the heavy child dp values are variable. Then, we can accelerate each chain in the heavy light decomposition of the tree. To get the matrix representation of each transition to the heavy child, there are 5 cases when considering a $dp[j][0/1/2]$ -> $dp[j][2]$ transiton where $dp[j][0]$ is the min, $dp[j][1]$ is the min, and $dp[j][2]$ is the min, $dp[j][2] - \min(dp[j][0], dp[j][2])$ is the optimal added value, or $dp[j][0] - min(dp[j][0], dp[j][1], dp[j][2])$, is the optimal added value. For each cell in the matrix, put the min of the $5$ cases. 736 737 Since you will only ever change hld chains $\log n$ times, the total complexity will be $n \log^2 n \cdot 3^3$. If we use balanced hld or other $n \log n$ hld techniques, then the complexity becomes $n \log^2 n$. Both solutions should pass under the given constraints. 738 739 **Code (C++)** 740 741 ``` 742 #ifndef LOCAL 743 #pragma GCC optimize("O3,unroll-loops") 744 #pragma GCC target("avx,avx2,fma") 745 #pragma GCC target("sse4,popcnt,abm,mmx,tune=native") 746 #endif 747 #include <bits/stdc++.h> 748 #include <ext/pb_ds/assoc_container.hpp> 749 #include <ext/pb_ds/tree_policy.hpp> 750 using namespace __gnu_pbds; 751 using namespace std; 752 753 #define pb push_back 754 #define ff first 755 #define ss second 756 757 typedef long long ll; 758 typedef long double ld; 759 typedef pair<int, int> pii; 760 typedef pair<ll, ll> pll; 761 typedef pair<ld, ld> pld; 762 763 const int INF = 1e9; 764 const ll LLINF = 1e18; 765 const int MOD = 1e9 + 7; 766 767 template<class K> using sset = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>; 768 769 inline ll ceil0(ll a, ll b) { 770 return a / b + ((a ^ b) > 0 && a % b); 771 } 772 773 void setIO() { 774 ios_base::sync_with_stdio(0); cin.tie(0); 775 } 776 777 struct Matrix { 778 779 array<array<ll, 3>, 3> mat; 780 781 array<ll, 3> &operator[](int x){ 782 return mat[x]; 783 } 784 785 const array<ll, 3> &operator[](int x) const { 786 return mat[x]; 787 } 788 789 Matrix(){ 790 for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) mat[i][j] = 0; 791 } 792 793 Matrix operator*(const Matrix &x){ 794 Matrix ret; 795 for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) ret[i][j] = LLINF; 796 for(int i = 0; i < 3; i++){ 797 for(int k = 0; k < 3; k++){ 798 for(int j = 0; j < 3; j++){ 799 ret[i][j] = min(ret[i][j], mat[i][k] + x[k][j]); 800 } 801 } 802 } 803 return ret; 804 } 805 806 Matrix &operator*=(const Matrix &x){ 807 (*this) = (*this) * x; 808 return *this; 809 } 810 }; 811 812 struct fastset { 813 814 priority_queue<ll, vector<ll>, greater<ll>> q, rem; 815 816 void insert(ll x){ 817 q.push(x); 818 } 819 820 void erase(ll x){ 821 rem.push(x); 822 } 823 824 ll query(){ 825 while(rem.size() && q.top() == rem.top()){ 826 rem.pop(); 827 q.pop(); 828 } 829 return q.top(); 830 } 831 832 void clear(){ 833 while(q.size()) q.pop(); 834 while(rem.size()) rem.pop(); 835 } 836 }; 837 838 vector<int> g[500005]; 839 int sub[500005]; 840 int head[500005]; 841 int par[500005]; 842 int tim = 0; 843 vector<int> chain[500005]; 844 int weight[500005]; 845 846 void dfs1(int x){ 847 sub[x] = 1; 848 for(int &i : g[x]){ 849 dfs1(i); 850 sub[x] += sub[i]; 851 if(sub[i] > sub[g[x][0]]) swap(i, g[x][0]); 852 } 853 } 854 855 int in[500005], out[500005]; 856 int dir[500005]; 857 858 void dfs2(int x, int p){ 859 chain[head[x]].pb(x); 860 par[x] = p; 861 weight[x] = 1; 862 in[x] = tim++; 863 for(int i : g[x]){ 864 head[i] = (i == g[x][0] ? head[x] : i); 865 dfs2(i, x); 866 if(i != g[x][0]) weight[x] += sub[i]; 867 } 868 out[x] = tim - 1; 869 } 870 871 Matrix dp[500005]; 872 Matrix cum[500005]; 873 int rt[500005]; 874 int left0[500005], right0[500005], ppar[500005]; 875 876 int dnq(int l, int r, int p, const vector<int> &v){ 877 if(l > r) return 0; 878 int sum = 0; 879 for(int i = l; i <= r; i++) sum += weight[v[i]]; 880 int cur = 0; 881 int mid = -1; 882 for(int i = l; i <= r; i++){ 883 cur += weight[v[i]]; 884 if(cur >= sum/2){ 885 mid = i; 886 break; 887 } 888 } 889 if(p == -1) ppar[v[mid]] = v[mid]; 890 else ppar[v[mid]] = p; 891 left0[v[mid]] = dnq(l, mid - 1, v[mid], v); 892 right0[v[mid]] = dnq(mid + 1, r, v[mid], v); 893 return v[mid]; 894 } 895 896 void merge(int x){ 897 if(right0[x] && left0[x]){ 898 cum[x] = cum[left0[x]]*dp[x]*cum[right0[x]]; 899 } else if(left0[x] && !right0[x]){ 900 cum[x] = cum[left0[x]]*dp[x]; 901 } else if(right0[x] && !left0[x]){ 902 cum[x] = dp[x]*cum[right0[x]]; 903 } else { 904 cum[x] = dp[x]; 905 } 906 } 907 908 void pull(int x){ 909 while(x != rt[x]){ 910 merge(x); 911 x = ppar[x]; 912 } 913 merge(x); 914 } 915 916 ll a[500005], b[500005], c[500005]; 917 ll dp0[500005][3]; 918 919 void dfs3(int x){ 920 dp0[x][0] = a[x]; 921 dp0[x][2] = b[x] + c[x]; 922 ll deg1 = a[x] + c[x], deg2 = b[x] + a[x] + c[x]; 923 ll mn1 = LLINF, mn2 = LLINF; 924 for(int i : g[x]){ 925 dfs3(i); 926 dp0[x][0] += dp0[i][0]; 927 dp0[x][2] += dp0[i][2]; 928 deg1 += min(dp0[i][0], dp0[i][1]); 929 deg2 += min({dp0[i][0], dp0[i][1], dp0[i][2]}); 930 mn1 = min(mn1, max((ll)0, dp0[i][1] - dp0[i][0])); 931 mn2 = min(mn2, max((ll)0, min(dp0[i][1], dp0[i][2]) - dp0[i][0])); 932 } 933 dp0[x][1] = min(deg1 + mn1, deg2 + mn2); 934 } 935 936 fastset deg1[500005], deg2[500005]; 937 ll sum0[500005], sum2[500005], sum01[500005], sum012[500005]; 938 939 void rebuild(int x){ 940 dp[x][0][0] = a[x] + sum0[x]; 941 dp[x][0][1] = LLINF; 942 dp[x][0][2] = LLINF; 943 if(g[x].size()){ 944 dp[x][1][0] = min(a[x] + b[x] + c[x] + deg2[x].query() + sum012[x], a[x] + c[x] + deg1[x].query() + sum01[x]); 945 dp[x][1][1] = min(a[x] + c[x] + sum01[x], a[x] + b[x] + c[x] + sum012[x]); 946 dp[x][1][2] = a[x] + b[x] + c[x] + sum012[x]; 947 } else { 948 dp[x][1][0] = dp[x][1][1] = dp[x][1][2] = LLINF; 949 } 950 dp[x][2][0] = LLINF; 951 dp[x][2][1] = LLINF; 952 dp[x][2][2] = b[x] + c[x] + sum2[x]; 953 } 954 955 ll eval(int x, int ind){ 956 return min({cum[rt[x]][ind][0], cum[rt[x]][ind][1], cum[rt[x]][ind][2]}); 957 } 958 959 void rem(int x){ 960 while(head[x] != 1){ 961 if(x == head[x]){ 962 ll v0 = eval(x, 0), v1 = eval(x, 1), v2 = eval(x, 2); 963 deg1[par[x]].erase(max((ll)0, v1 - v0)); 964 deg2[par[x]].erase(max((ll)0, min(v1, v2) - v0)); 965 sum012[par[x]] -= min({v0, v1, v2}); 966 sum01[par[x]] -= min(v0, v1); 967 sum0[par[x]] -= v0; 968 sum2[par[x]] -= v2; 969 x = par[x]; 970 } 971 x = head[x]; 972 } 973 } 974 975 void add(int x){ 976 while(head[x] != 1){ 977 if(x == head[x]){ 978 ll v0 = eval(x, 0), v1 = eval(x, 1), v2 = eval(x, 2); 979 deg1[par[x]].insert(max((ll)0, v1 - v0)); 980 deg2[par[x]].insert(max((ll)0, min(v1, v2) - v0)); 981 sum012[par[x]] += min({v0, v1, v2}); 982 sum01[par[x]] += min(v0, v1); 983 sum0[par[x]] += v0; 984 sum2[par[x]] += v2; 985 rebuild(par[x]); 986 pull(par[x]); 987 x = par[x]; 988 } 989 x = head[x]; 990 } 991 } 992 993 int main(){ 994 setIO(); 995 int t; 996 cin >> t; 997 while(t--){ 998 int n, q; 999 cin >> n >> q; 1000 for(int i = 2; i <= n; i++){ 1001 int x; 1002 cin >> x; 1003 g[x].pb(i); 1004 } 1005 ll sum = 0; 1006 for(int i = 1; i <= n; i++) cin >> b[i], sum += b[i]; 1007 dfs1(1); 1008 head[1] = 1; 1009 dfs2(1, 1); 1010 dfs3(1); 1011 for(int i = 1; i <= n; i++){ 1012 if(chain[i].size()){ 1013 int p = dnq(0, chain[i].size() - 1, -1, chain[i]); 1014 for(int j : chain[i]) rt[j] = p; 1015 } 1016 } 1017 for(int i = 1; i <= n; i++){ 1018 deg1[i].insert(LLINF); 1019 deg2[i].insert(LLINF); 1020 for(int j : g[i]){ 1021 if(head[j] == head[i]) continue; 1022 deg1[i].insert(max((ll)0, dp0[j][1] - dp0[j][0])); 1023 deg2[i].insert(max((ll)0, min(dp0[j][1], dp0[j][2]) - dp0[j][0])); 1024 sum012[i] += min({dp0[j][0], dp0[j][1], dp0[j][2]}); 1025 sum01[i] += min(dp0[j][0], dp0[j][1]); 1026 sum0[i] += dp0[j][0]; 1027 sum2[i] += dp0[j][2]; 1028 } 1029 rebuild(i); 1030 pull(i); 1031 } 1032 while(q--){ 1033 int t, x, v; 1034 cin >> t >> x >> v; 1035 rem(x); 1036 if(t == 1) a[x] += v; 1037 else c[x] += v, sum += v; 1038 rebuild(x); 1039 pull(x); 1040 add(x); 1041 cout << (min({eval(1, 0), eval(1, 1), eval(1, 2)}) == sum ? "YES" : "NO") << "\n"; 1042 } 1043 tim = 0; 1044 for(int i = 1; i <= n; i++){ 1045 a[i] = b[i] = c[i] = 0; 1046 g[i].clear(); 1047 chain[i].clear(); 1048 deg1[i].clear(); 1049 deg2[i].clear(); 1050 sum0[i] = sum2[i] = sum01[i] = sum012[i] = 0; 1051 } 1052 } 1053 } 1054 ``` 1055 1056 **Solution 2** 1057 1058 There also exists a solution without flows. Thanks to [rainboy](/profile/rainboy "Master rainboy") for discovering it during testing! 1059 1060 Lets greedily assign the growth events. We will always try to use the growth events to satisfy harvest events or required peaches in its subtree, and if there is any excess then we give it to the parent's required peaches. Similarly, we will always use harvest events on growth events in its subtree. Lets define a $dp[u]$ for each node $u$. If $dp[x] \gt 0$ then it means we can give $dp[u]$ growths to $u$'s parent. Otherwise, it means $dp[u]$ requires $-dp[u]$ growths from its ancestors. Let $pos_u$ denote the sum of positive $dp[v]$ where $v$ is a child a of $u$, and $neg_u$ denote the sum of negative $dp[v]$. First we used the excess growth to satisfy the required peaches, so we can set $b_u = \max(0, b_u - pos_u)$. Then we distribute the growth events at node $u$ to satisfy the requirements in the subtree. Define $a_i$ as the number of growth events on node $i$ and $c_i$ as the number of harvest events on node $i$. To account for the harvest events at node $i$, we can define $bal_u = \text{sum of } a_i \text{ in u's subtree} - \text{sum of } b_i \text{ in u's subtree} - \text{sum of } c_i \text{ in u's subtree}$. We know that $dp[u] \le bal_u$, and as it turns out, as long as we keep $bal_u$ as an upper bound on $dp[u]$, the harvest events will always be satisfied. Why? $a_u + neg_u - \max(0, b_u - pos_u)$ is the assignment of growth events without considering harvest events. The amount of unused growth events in the subtree of $u$ is given by $bal_u - (a_u + neg_u - \max(0, b_u - pos_u)) + c_u$. If $a_u + neg_u - \max(0, b_u - pos_u) \le bal_u$, then it means we can use all of our harvest events on unused growth events in the subtree. If $a_u + neg_u - \max(0, b_u - pos_u) \gt bal_u$, then it means we will use all of our harvest events but still have $bal_u - (a_u + neg_u - \max(0, b_u - pos_u))$ harvest events remaining. Thus, we can formulate our dp as $dp[u] = \min(a_u + neg_u - \max(0, b_u - pos_u), bal_u)$. Let $v$ be the heavy child of $u$ and $pos'_u$ be the sum of positive dp excluding $v$ and $neg'_u$ be the sum of positive dp excluding $v$. Then, we can rewrite our dp as $dp[u] = \min(dp[v] + a_u + neg'_u - \max(0, b_u - pos'_u), a_u + neg'_u, bal_u)$. Define $x_u = a_u + neg'_u - \max(0, b_u - pos'_u)$ and $y_u = a_u + neg'_u$. Then $dp[u] = \min(dp[v] + x_u, y_u, bal_u)$. This can be accelerated by representing the transition as a matrix and accelerating it using dynamic dp. However, we can also notice that the dp can be represented as the smallest $x_1 + x_2 + \ldots + x_{i - 1} + \min(y_i, bal_i)$ over all prefixes of each heavy light decomposition chain. Thus, we can maintain the dp by using a range add and prefix min segment tree. 1061 1062 **Code (C++)** 1063 1064 ``` 1065 #include <stdio.h> 1066 #include <stdlib.h> 1067 #include <string.h> 1068 1069 #define N 300000 1070 #define N_ (1 << 19) /* N_ = pow2(ceil(log2(N))) */ 1071 #define INF 0x3f3f3f3f3f3f3f3fLL 1072 1073 long long min(long long a, long long b) { return a < b ? a : b; } 1074 long long max(long long a, long long b) { return a > b ? a : b; } 1075 1076 int *ej[N], eo[N], n; 1077 1078 void append(int i, int j) { 1079 int o = eo[i]++; 1080 1081 if (o >= 2 && (o & o - 1) == 0) 1082 ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]); 1083 ej[i][o] = j; 1084 } 1085 1086 int dd[N], pp[N], qq[N], jj[N], ta[N], tb[N], qu[N]; 1087 int bb[N]; long long aa[N], zz[N], zzp[N], zzn[N]; 1088 1089 int dfs1(int i, int d) { 1090 int o, s, k_, j_; 1091 1092 dd[i] = d; 1093 s = 1, k_ = 0, j_ = -1; 1094 zz[i] = -bb[i]; 1095 for (o = eo[i]; o--; ) { 1096 int j = ej[i][o], k = dfs1(j, d + 1); 1097 1098 s += k; 1099 if (k_ < k) 1100 k_ = k, j_ = j; 1101 zz[i] += zz[j]; 1102 } 1103 qq[i] = j_, jj[i] = j_ == -1 ? i : jj[j_]; 1104 return s; 1105 } 1106 1107 int t_; 1108 1109 void dfs2(int i, int q) { 1110 int o, j_; 1111 1112 qu[ta[i] = t_++] = i; 1113 j_ = qq[i], qq[i] = q; 1114 if (j_ != -1) 1115 dfs2(j_, q); 1116 for (o = eo[i]; o--; ) { 1117 int j = ej[i][o]; 1118 1119 if (j != j_) 1120 dfs2(j, j); 1121 } 1122 tb[i] = t_; 1123 } 1124 1125 long long stx[N_ * 2], sty[N_ * 2], stz[N_ * 2], lz[N_]; int h_, n_; 1126 1127 void put(int i, long long x) { 1128 stz[i] += x; 1129 if (i < n_) 1130 lz[i] += x; 1131 } 1132 1133 void pus(int i) { 1134 if (lz[i]) 1135 put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0; 1136 } 1137 1138 void pul(int i) { 1139 if (!lz[i]) { 1140 int l = i << 1, r = l | 1; 1141 1142 stx[i] = stx[l] + stx[r]; 1143 sty[i] = min(sty[l], stx[l] + sty[r]); 1144 stz[i] = min(stz[l], stx[l] + stz[r]); 1145 } 1146 } 1147 1148 void push(int i) { 1149 int h; 1150 1151 for (h = h_; h > 0; h--) 1152 pus(i >> h); 1153 } 1154 1155 void pull(int i) { 1156 while (i > 1) 1157 pul(i >>= 1); 1158 } 1159 1160 void build() { 1161 int i, j, a, o; 1162 h_ = 0; 1163 1164 while (1 << h_ < n) 1165 h_++; 1166 n_ = 1 << h_; 1167 memset(stx, 0, n_ * 2 * sizeof *stx); 1168 memset(sty, 0, n_ * 2 * sizeof *sty); 1169 memset(stz, 0, n_ * 2 * sizeof *stz); 1170 memset(lz, 0, n_ * sizeof *lz); 1171 memset(aa, 0, n * sizeof *aa); 1172 memset(zzp, 0, n * sizeof *zzp); 1173 memset(zzn, 0, n * sizeof *zzn); 1174 for (i = 0; i < n; i++) { 1175 a = ta[i]; 1176 stz[n_ + a] = zz[i]; 1177 for (o = eo[i]; o--; ) { 1178 j = ej[i][o]; 1179 if (qq[j] == j) 1180 zzn[i] += -zz[j]; 1181 } 1182 stx[n_ + a] = -zzn[i] - bb[i]; 1183 sty[n_ + a] = -zzn[i]; 1184 } 1185 for (i = n_ - 1; i > 0; i--) 1186 pul(i); 1187 } 1188 1189 void upd(int i) { 1190 int i_ = n_ + ta[i]; 1191 1192 push(i_); 1193 stx[i_] = aa[i] - zzn[i] - max(bb[i] - zzp[i], 0); 1194 sty[i_] = aa[i] - zzn[i]; 1195 pull(i_); 1196 } 1197 1198 void update_z(int l, int r, long long x) { 1199 int l_ = l += n_, r_ = r += n_; 1200 1201 push(l_), push(r_); 1202 for ( ; l <= r; l >>= 1, r >>= 1) { 1203 if ((l & 1) == 1) 1204 put(l++, x); 1205 if ((r & 1) == 0) 1206 put(r--, x); 1207 } 1208 pull(l_), pull(r_); 1209 } 1210 1211 long long query(int l, int r) { 1212 long long xl, yl, zl, xr, yr, zr; 1213 1214 push(l += n_), push(r += n_); 1215 xl = 0, yl = INF, zl = INF, xr = 0, yr = INF, zr = INF; 1216 for ( ; l <= r; l >>= 1, r >>= 1) { 1217 if ((l & 1) == 1) { 1218 yl = min(yl, xl + sty[l]), zl = min(zl, xl + stz[l]), xl += stx[l]; 1219 l++; 1220 } 1221 if ((r & 1) == 0) { 1222 yr = min(sty[r], yr == INF ? INF : stx[r] + yr), zr = min(stz[r], zr == INF ? INF : stx[r] + zr), xr += stx[r]; 1223 r--; 1224 } 1225 } 1226 return min(min(xl + xr, min(yl, yr == INF ? INF : xl + yr)), min(zl, zr == INF ? INF : xl + zr)); 1227 } 1228 1229 int main() { 1230 int t; 1231 1232 scanf("%d", &t); 1233 while (t--) { 1234 int q_, i, p, q; 1235 1236 scanf("%d%d", &n, &q_); 1237 for (i = 0; i < n; i++) 1238 ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0; 1239 pp[0] = -1; 1240 for (i = 1; i < n; i++) { 1241 scanf("%d", &pp[i]), pp[i]--; 1242 append(pp[i], i); 1243 } 1244 for (i = 0; i < n; i++) 1245 scanf("%d", &bb[i]); 1246 dfs1(0, 0); 1247 t_ = 0, dfs2(0, 0); 1248 build(); 1249 while (q_--) { 1250 int t, x; 1251 1252 scanf("%d%d%d", &t, &i, &x), i--; 1253 if (t == 2) 1254 x = -x; 1255 if (t == 1) 1256 aa[i] += x, upd(i); 1257 while (i >= 0) { 1258 q = qq[i], p = pp[q]; 1259 if (p >= 0) { 1260 if (zz[q] > 0) 1261 zzp[p] -= zz[q]; 1262 else 1263 zzn[p] -= -zz[q]; 1264 } 1265 update_z(ta[q], ta[i], x); 1266 zz[q] = query(ta[q], ta[jj[q]]); 1267 if (p >= 0) { 1268 if (zz[q] > 0) 1269 zzp[p] += zz[q]; 1270 else 1271 zzn[p] += -zz[q]; 1272 upd(p); 1273 } 1274 i = p; 1275 } 1276 printf(zz[0] >= 0 ? "YES\n" : "NO\n"); 1277 } 1278 for (i = 0; i < n; i++) 1279 free(ej[i]); 1280 } 1281 return 0; 1282 } 1283 ```